299
правок
Изменения
→Случай произвольного графа
Итак, пусть мы имеем <tex>n</tex>-дольный граф <tex>G^l</tex>, доли которого <tex>V_i=V_i(G^l)</tex> (где <tex>i\in [1..n]</tex>). Пусть с парой строк (и, соответственно, долей) <tex>i,j</tex> мы еще не выполняли шаг. Очевидно, граф <tex>G_{i,j}=G^l(V_i\cup V_j)</tex> двудолен и для него по лемме существует двудольный рамсеевский граф <tex>P_{i,j}</tex>. Более того если вершины <tex>P_{i,j}</tex> разбиты на две доли <tex>W_i</tex> и <tex>W_j</tex>, то для любой раскраски рёбер в два цвета существует одноцветное погружение <tex>\phi</tex> графа <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> в котором <tex>\phi(V_i)\subset W_i</tex> и <tex>\phi(V_j)\subset W_j</tex>. Назовём таксе погружение одноцветным.
Перейдём к построению Ge<tex>G^{l+1}</tex>. Заменим К <tex>V_i</tex> на Wi <tex>W_i</tex> и Vj <tex>V_j</tex> на Wj. проведём <tex>W_j</tex>, проведем между зтими этими долями Есе все рёбра графа Pitj<tex>P_{i,j}</tex>. Наша цель в темтом, чтобы для любого погружения Gitj <tex>G_{i,j}</tex> в Р^ <tex>P_{i,j}</tex> была содержащая его кспия Ge копия <tex>G^l</tex> (причём причем доли этой копии лежали в соответствующих строках таблицы графа<tex>G^{l+1}</tex> Занумеруем всевозможные погружения <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex>: пусть это <tex>G_{i,j}(1),...,G_{i,j}(q)</tex>. Каждому погружению <tex>G_{i,j}(s)</tex> мы поставим в соответствие отдельные копии всех отличных от <tex>V_i</tex> и <tex>V_j</tex> долей: <tex>V_1(s),...,V_n(s)</tex>. Положим <tex>V_i(s)=V(G_{i,j}(s))\cap W_i</tex> и <tex>V_j(s)=V(G_{i,j}(s))\cap W_j</tex>. На этих долях построим копию графа <tex>G^l</tex>. В результате для каждого погружения графа <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> мы построили свою копию графа <tex>G^l</tex>. '''Выделение одноцветного индуцированного подграфа.'''
Итак, докажем, что G = Gc" и есть рамсеевский граф для Н. Пусть Ри - ■ ■ iPci — именно такая нумерация пар строк в нашей таблице, ь порядке которой совершались шаги перестройки графа. Еассмстрим произвольную раскраску рёбер р графа G ь два цвета и докажем следующий факт.
Для каждссс £ е [0..С2] существует изоморфные G1 иьсуьирсван-
ный поограф графа G. б котором для пар строк ре+г- .., рс% все рёбра между вершинами ссответстеукших пар строк в раскраске р одноцветны
Доказательство. Индукция с обратным ходом ст £ — С2п к £ — 0. База для £ = С\ очеЕидна. Докажем переход £ ^ £ — 1
Итак рассмотрим наш изоморфный G1 подграф который мы для простоты будем обозначать Ge и пару строку е нем пусть это строки г и j. a Pij и Gitj — те двудольные графы между этими строками, что списаны в шаге псстроения. Так как Pjj (подграф графа Ge) — рамссеЕСкий граф для Gij. мы межем выбрать одноцветное е раскраске р погружение Gij в Pitj и соответствующая ему по построению копия Ge_1 будет искомым (из построения очевидно, чте индуиирсьанным!) подграфом Ge а значит, bG □
Таким образом, сушестнует иземерфный G0 индуцированный подграф графа G. е кстсрем для каждой пары стрск i,j Есе ребра между Есршинами состЕСтстЕуюших строк одноцветны е раскраске р. Будем обозначать зтот граф просто G0. Бассмстрим граф Кп Еершины которого соответствуют строкам таблицы и искрасим каждое ребро в пест в который покрашены рёбра G0 между соответствующими строками Так как п = r(k,k) существуют к Есршин, между которыми ьсе рёбра одноцветны. Рассмотрим столбец графа G°, е котором Н размещён именно е строчках. соответствующих этим к вершинам. Подграф Н' графа G0 на вершинах этого столбца и соответствующих строчках из с мор фен Н пс построению является индугшрсЕанным подграфом графа G0 и все его рёбра одноцветны в раскраске р. Остаётся лишь заметить, что Я' — индуцированный подграф графа G.
}}
