442
правки
Изменения
м
}}
==Индуцированная теорема Рамсея==
Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.
{{Определение
|id=def9
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}
При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>.
{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа существует рамсеевский граф
}}
===Случай двудольного графа===
Здесь мы будем рассматривать двудольный граф <tex>G</tex>, как
<tex>G=(V_1(G),V_2(G),E(G))</tex>,
где <tex>V_1(G)</tex> и <tex>V_2(G)</tex> — разбиение множества вершин <tex>V(G)</tex> на две доли, а рёбра соединяют вершины из разных долей.
{{Определение
|id=def10
|definition=
Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём погружением, если оно удовлетворяет двум условиям.<br>
1)<tex>\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)</tex><br>
2)<tex>\phi(u)\phi(v) \in E(G)</tex> тогда и только тогда когда <tex>uv\in E(H)</tex>
В этом случае будем говорить, что двудольный граф <tex>H</tex> погружён в двудольный граф <tex>G</tex> и использовать обозначение <tex>\phi(H)=G(\phi(V(H)))</tex>
}}
{{Утверждение
|id=u5|about=5
|statement=
Отметим, что если существует погружение <tex>\phi</tex> двудольного графа <tex>H</tex> в двудольный граф <tex>G</tex> то индуцированный подграф <tex>\phi(H)</tex> графа <tex>G</tex> изоморфен <tex>H</tex>
}}
Напомним, что для множества <tex>X</tex> через <tex>X^k</tex> мы обозначаем множество всех <tex>k</tex>-элементных подмножеств множества <tex>X</tex>.
{{Определение
|id=def11
|definition=Назовем особым двудольный граф вида
<tex>H=(V,V^k,E(H))</tex>, где <tex>E(H)=</tex>{<tex>xY|x\in V,Y\in V^k, x\in Y</tex>}
}}
{{Лемма
|id=l2|about=2
|statement=Любой двудольный граф может быть погружен в особый двудольный граф.
|proof=
Рассмотрим произвольный двудольный граф <tex>P</tex>, пусть <tex>V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}</tex>. Положим
<tex>V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}</tex>
Построим погружение <tex>P</tex> в особый двудольный граф <tex>H=(V,V^{n+1},E)</tex>.
Изначально положим <tex>\phi(a_i)=x_i</tex>. Попробуем построить такое множество <tex>Y_j\in V^{n+1}</tex>, что <tex>\phi(b_j)=Y_j</tex>. По определению погружения и множества <tex>E(H)</tex>, должно выполняться условие:<br>
<tex>Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)</tex>
Условие оставляет незаполненными <tex>n+1-d_P(b_j)\ge 1</tex> элементов множества <tex>Y_j</tex> (единственное ограничение эти элементы не могут быть вершинами <tex>x_1,...,x_n</tex>). Поместим в <tex>Y_j</tex> элемент-индекс <tex>z_j</tex> (чтобы <tex>Y_j\not=Y_l</tex> при <tex>j \not=l</tex>, и дополним произвольно элементами из <tex>y_1,...,y_n</tex>, чтобы в множестве <tex>Y_j</tex> было ровно <tex>n+1</tex> элементов.
}}
{{Лемма
|id=l3|about=3
|statement=Для любого двудольного графа <tex>H</tex> существует такой двудольный граф <tex>G</tex>, что для любой раскраски рёбер <tex>G</tex> в два цвета обязательно существует погружение <tex>\phi</tex> графа <tex>H</tex> в граф <tex>G</tex> в котором все рёбра <tex>\phi(H)</tex> одноцветны.
|proof=
{{Утверждение
|id=u6|about=6
|statement=
Разумеется, указанный в условии [[#l3|леммы 3]] граф <tex>G</tex> будет рамсеевским графом для <tex>H</tex>. Утверждение леммы более сильное: мы дополнительно требуем, чтобы все вершины одной доли <tex>H</tex> можно было погрузить в одну долю графа <tex>G</tex>.
}}
Ввиду [[#l2|леммы 2]] достаточно доказать утверждение для особого двудольного графа <tex>H=(V,V^k,E(H))</tex>. Пусть <tex>|V|=n</tex>. Докажем что рамсеевским графом для <tex>H</tex> будет особый двудольный граф <tex>G=(U,U^{2k-1},E(G))</tex>, где<br>
<tex>|U|=r_{2k-1}(2C^k_{2k-1};kn+k-1,...,kn+k-1).</tex> '''**'''<br>
Рассмотрим произвольную раскраску рёбер графа <tex>G</tex> в два цвета 1 и 2. Каждое множество <tex>Y\in U^{2k-1}</tex> смежно как вершина особого двудольного графа <tex>G</tex> с <tex>2k-1</tex> вершиной, хотя бы <tex>k</tex> из этих рёбер имеет одинаковый цвет. Выберем и зафиксируем для каждого множества <tex>Y</tex> его подмножество <tex>S(Y)</tex>, состоящее из <tex>k</tex> вершин доли <tex>U</tex> соединённых с <tex>Y</tex> рёбрами одинакового цвета. Пусть <tex>c(Y)\in \{1,2\}</tex> — это цвет рёбер соединяющий <tex>Y</tex> с вершинами из <tex>S(Y)</tex>.
Можно считать, что элементы <tex>U</tex> упорядочены. Тогда элементы каждого множества <tex>Y\in U^{2k-1}</tex> будут упорядочены. Обозначим через <tex>\sigma(Y)</tex> множество номеров <tex>k</tex> элементов множества <tex>S(Y)</tex> в порядке элементов множества <tex>Y</tex>. Тогда <tex>\sigma(Y)</tex> может принимать ровно <tex>C^k_{2k-1}</tex> значений.
Покрасим множество <tex>U^{2k-1}</tex> (то есть все <tex>(2k-1)</tex>-элементные подмножества <tex>U</tex>) в <tex>2C^k_{2k-1}</tex>цветов: цветом подмножества <tex>Y</tex> будет пара <tex>(\sigma(Y),c(Y))</tex>. Из выбора размера множества <tex>U</tex> (см. условие **) следует, что ceotcndetn такое подмножество <tex>W\subset U</tex>, что <tex>|W|=kn+k-1</tex> и все подмножества <tex>Y\subset W^{2k-1}</tex> имеют одинаковый цвет <tex>(\sigma(Y),c(Y))</tex> (не умаляя общности будем считать, что <tex>\sigma(Y)=\sigma, c(Y)=1)</tex>. Мы найдём погружение графа <tex>H</tex> в <tex>G(W)</tex>, все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.
Занумеруем элементы множества <tex>W</tex> в порядке их следования в <tex>U</tex>: пусть <tex>W=\{w_1,...,w_{kn+k-1}\}</tex>. Введем обозначения
<tex>t_j=w_kj, T=\{t_1,...,t_n\}, V=\{a_1,...,a_n\}</tex>.
Положим <tex>\phi(a_i)=t_i</tex>. Остаётся корректно определить <tex>\phi(Z)</tex> для каждого множества <tex>Z\in V^k</tex>. Прежде чем построить <tex>\phi(Z)=Y\in U^{2k-1}</tex> мы положим <tex>S(Y)=\{\phi(x):x\in Z\}</tex>. Из определения погружения понятно, что тогда должно выполняться условие <tex>S(Y)=Y\cap T</tex>, а следовательно, нам нужно дополнить множество <tex>Y</tex> еще <tex>k-1</tex> элементами, не входящими в множество <tex>T</tex>. Мы сделаем это так, чтобы множество порядков номеров элементов множества <tex>S(Y)</tex> среди элементов множества <tex>Y</tex> было <tex>\sigma(Y)=\sigma</tex>: так как <tex>t_i=w_ki</tex>, не входящих в <tex>T</tex> элементов <tex>W</tex> хватит, чтобы обеспечить это.
Так как по выбору множества <tex>W</tex> мы имеем <tex>\sigma(Y)=\sigma</tex>, множество <tex>S(Y)</tex> выбрано корректно и, опять же в силу выбора <tex>W</tex>, все рёбра особого двудольного графа <tex>G</tex> между вершинами из <tex>S(Y)=\{\phi(x):x\in Z\}</tex> и <tex>Y=\phi(Z)</tex> покрашены в цвет 1. В завершение остается лишь добавить, что при <tex>Z\not=Z'</tex> мы по построению имеем <tex>S(\phi(Z))\not=S(\phi(Z'))</tex>, поэтому <tex>\phi(Z)\not=\phi(Z')</tex>. Таким образом искомое погружение построено.
}}
===Случай произвольного графа===
{{Теорема
|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>
Занумеруем всевозможные погружения <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>.
'''Выделение одноцветного индуцированного подграфа.'''
Итак, докажем, что <tex>G=G^{C^2_n}</tex> и есть рамсеевский граф для <tex>H</tex>. Пусть <tex>p_1,...,p_{C^2_n}</tex> — именно такая нумерация пар строк в нашей таблице, в порядке которой совершались шаги перестройки графа. Рассмотрим произвольную раскраску рёбер <tex>\rho</tex> графа <tex>G</tex> в два цвета и докажем следующий факт.
{{Утверждение
|id=u7|about=7
|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=
Индукция с обратным ходом от <tex>l=C^2_n</tex> к <tex>l=0</tex>. База для <tex>l=C^2_n</tex> очевидна. Докажем переход <tex>l\rightarrow l-1</tex>
Итак рассмотрим наш изоморфный <tex>G^l</tex> подграф, который мы для простоты будем обозначать <tex>G^l</tex> и пару строку <tex>p_l</tex> в нем: пусть это строки <tex>i</tex> и <tex>j</tex>, a <tex>P_{i,j}</tex> и <tex>G_{i,j}</tex> — те двудольные графы между этими строками, что описаны в шаге построения. Так как <tex>P_{i,j}</tex> (подграф графа <tex>G^l</tex>) — рамсеевский граф для <tex>G_{i,j}</tex>, мы можем выбрать одноцветное в раскраске <tex>\rho</tex> погружение <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> и соответствующая ему по построению копия <tex>G^{l-1}</tex> будет искомым (из построения очевидно, что индуцированным!) подграфом <tex>G^l</tex> а значит, и <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>.
→Индуцированная теорема Рамсея
<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#l1|лемме 1]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах в частности, дерево, изоморфное <tex>T_n</tex>.
}}
