299
правок
Изменения
→Случай двудольного графа
}}
{{Утверждение
|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=def10
|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=
{{Лемма
|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>. Введем обозначения
