Изменения

Перейти к: навигация, поиск

Теория Рамсея

217 байт добавлено, 02:36, 7 января 2014
→‎Случай произвольного графа
|statement=Для каждого <tex>l\in [0..C^2_n]</tex> существует изоморфный <tex>G^l</tex> индуцированный подграф графа <tex>G</tex>, в котором для пар строк <tex>p_{l+1},...,p_{C^2_n}</tex> все рёбра между вершинами соответствующих пар строк в раскраске <tex>\rho</tex> одноцветны.
|proof=
Доказательство. Индукция с обратным ходом ст £ — С2п от <tex>l=C^2_n</tex> к £ — <tex>l=0</tex>. База для £ <tex>l= С\ очеЕиднаC^2_n</tex> очевидна. Докажем переход £ ^ £ — <tex>l\rightarrow l-1</tex> Итак рассмотрим наш изоморфный G1 <tex>G^l</tex> подграф , который мы для простоты будем обозначать Ge <tex>G^l</tex> и пару строку е <tex>p_l</tex> в нем : пусть это строки г <tex>i</tex> и <tex>j. </tex>, a Pij <tex>P_{i,j}</tex> и Gitj <tex>G_{i,j}</tex> — те двудольные графы между этими строками, что спи­саны описаны в шаге псстроенияпостроения. Так как Pjj <tex>P_{i,j}</tex> (подграф графа Ge<tex>G^l</tex>) — рамссеЕСкий рамсеевский граф для Gij. <tex>G_{i,j}</tex>, мы межем можем выбрать одноцветное е в раскраске р <tex>\rho</tex> погружение Gij <tex>G_{i,j}</tex> в Pitj <tex>P_{i,j}</tex> и соответствующая ему по построению копия Ge_1 <tex>G^{l-1}</tex> будет иско­мым искомым (из построения очевидно, чте индуиирсьаннымчто индуцированным!) подграфом Ge <tex>G^l</tex> а значит, bG и <tex>G</tex> }}
Таким образом, существует изоморфный <tex>G^0</tex> индуцированный под­граф графа <tex>G</tex>, в котором для каждой пары строк <tex>i,j</tex> все ребра между вершинами соответствующих строк одноцветны в раскраске <tex>\rho</tex>. Будем обозначать этот граф просто <tex>G^0</tex>. Рассмотрим граф <tex>K_n</tex>, вершины которого соответствуют строкам таблицы и покрасим каждое ребро в цвет, в который покрашены рёбра <tex>G^0</tex> между соответствующими строками. Так как <tex>n=r(k,k)</tex>, существуют <tex>k</tex> вершин, между которыми все рёбра одноцветны. Рассмотрим столбец графа <tex>G^0</tex>, в котором <tex>H</tex> размещён именно в строчках, соответствующих этим <tex>k</tex> вершинам. Подграф <tex>H'</tex> графа <tex>G^0</tex> на вершинах этого столбца и соответствующих строчках изоморфен <tex>H</tex>, по построению является индуцированным подграфом графа <tex>G^0</tex> и все его рёбра одноцветны в раскраске <tex>\rho</tex>. Остаётся лишь заметить, что <tex>H'</tex> — индуцированный подграф графа <tex>G</tex>.
}}
Kamigan4eg
299
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/35292»

Навигация