299
правок
Изменения
→Случай произвольного графа
===Случай произвольного графа===
{{Теорема
|id=ter7|about=7
|statement=Для произвольного графа <tex>H</tex> существует рамсеевский граф.
|proof=
Пусть <tex>k=v(H),n=r(k,k)</tex>. Пронумеруем вершины графа <tex>H</tex>. Построим граф <tex>G^0</tex> следующим образом: разместим его вершины в виде таблице <tex>n \times C^k_n</tex>. Таким образом в каждом столбце вершины окажутся пронумерованы числами от 1 до <tex>n</tex>, как соответствующие строки таблицы. В каждом столбце одним из <tex>C^k_n</tex> способов разместим граф <tex>H</tex> (каждый столбец соответствует одному из возможных способов размещения). Все рёбра графа <tex>G^0</tex> будут рёбрами указанных копий графа <tex>H</tex>.
Граф <tex>G^0</tex> является <tex>n</tex>-дольным, его естественное разбиение на доли задаётся таблицей: <tex>V_i(G^0)</tex> — это вершины, соответствующие <tex>i</tex> ряду таблицы. Мы последовательно в несколько шагов будем перестраивать наш граф с помощью [[#l3|леммы3]], так, чтобы вершины последующих графов также разбивались на <tex>n</tex> долей и записывались в виде таблицы. Каждый шаг будет соответствовать одной паре строк таблицы.
'''Шаг перестройки графа.'''
Итак, пусть мы имеем <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> двудолен и для него по [[#l3|лемме 3]] существует двудольный рамсеевский граф <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>. Назовём таксе погружение одноцветным.
Перейдём к построению <tex>G^{l+1}</tex>. Заменим <tex>V_i</tex> на <tex>W_i</tex> и <tex>V_j</tex> на <tex>W_j</tex>, проведем между этими долями все рёбра графа <tex>P_{i,j}</tex>. Наша цель в том, чтобы для любого погружения <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> была содержащая его копия <tex>G^l</tex> (причем доли этой копии лежали в соответствующих строках таблицы графа <tex>G^{l+1}</tex>
