Теория Рамсея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Существование. Оценки сверху)
(Экстремальные примеры и оценки снизу)
Строка 37: Строка 37:
 
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.
 
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.
 
{{Определение|id=def3
 
{{Определение|id=def3
|definition=Графом Рамсея <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).
+
|definition='''Графом Рамсея''' <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).
 
}}
 
}}
 
Граф <tex>R(3,3)</tex> — это цикл на пяти вершинах. Экстремальный граф <tex>R(3,4)</tex> — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы <tex>R(3,5)</tex> и <tex>R(4,4)</tex> имеют интересную числовую природу.
 
Граф <tex>R(3,3)</tex> — это цикл на пяти вершинах. Экстремальный граф <tex>R(3,4)</tex> — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы <tex>R(3,5)</tex> и <tex>R(4,4)</tex> имеют интересную числовую природу.

Версия 15:52, 28 ноября 2018

Теория Рамсея — раздел математики, названный в честь Фрэнка Рамсея, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

Числа Рамсея

Определение:
Кликой в неориентированном графе [math]G = (V, E)[/math] называется подмножество вершин [math]C \subseteq V[/math], такое что для любых двух вершин в [math]C[/math] существует ребро, их соединяющее.


Определение:
Числом Рамсея [math]r(m, n)[/math], где [math]m, n \in \mathbb N [/math] называют наименьшее из таких чисел [math]x \in \mathbb N[/math], что при любой раскраске ребер полного графа на [math]x[/math] вершинах в два цвета найдется клика на [math]n[/math] вершинах с ребром цвета [math]1[/math] или клика на [math]m[/math] вершинах с ребром цвета [math]2[/math].


Существование. Оценки сверху

Теорема (1):
[math]r(n,m) \le r(n,m-1)+r(n-1,m)[/math] . При этом если числа [math]r(n,m-1)[/math] и [math]r(n-1,m)[/math] четные, то неравенство принимает вид [math]r(n,m) \le r(n,m-1)+r(n-1,m) - 1[/math] .
Доказательство:
[math]\triangleright[/math]

[math]1)[/math] Докажем с помощью метода математической индукции по [math]n+m[/math].

База: [math]r(n,\;1) = r(1,\;n) = 1[/math], так как 1-вершинный граф можно считать полным графом любого цвета.

Индукционный переход: Пусть [math]n\gt 1[/math] и [math]m\gt 1[/math]. Рассмотрим полный чёрно-белый граф из [math]r(n-1,\;m)+r(n,\;m-1)[/math] вершин. Возьмём произвольную вершину [math]v[/math] и обозначим через [math]M[/math] и [math]N[/math] множества инцидентные [math]v[/math] в чёрном и белом подграфе соответственно. Так как в графе [math]r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 [/math] вершин, согласно принципу Дирихле, либо [math]|M|\geqslant r(n-1,\;m)[/math], либо [math]|N|\geqslant r(n,\;m-1)[/math].

Пусть [math]|M|\geqslant r(n-1,\;m)[/math]. Тогда либо в [math]M[/math] (и следовательно во всём графе) есть белый [math]K_m[/math], что завершает доказательство, либо в [math]M[/math] есть чёрный [math]K_{n-1}[/math], который вместе с [math]v[/math] образует чёрный [math]K_n[/math]. Случай [math]|N|\geqslant r(n,\;m-1)[/math] рассматривается аналогично.

[math]2)[/math] Предположим, [math]p=r(n-1,\;m)[/math] и [math]q=r(n,\;m-1)[/math] оба чётны. Положим [math]t=p+q-1[/math] и рассмотрим чёрно-белый граф из [math]t[/math] вершин. Если [math]d_i[/math] степень [math]i[/math]-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, [math]\sum_{i=1}^t d_i[/math] — чётно. Поскольку [math]t[/math] нечётно, должно существовать чётное [math]d_i[/math]. Для определённости положим, что [math]d_1[/math] чётно. Обозначим через [math]M[/math] и [math]N[/math] вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда [math]|M|=d_1[/math] и [math]|N|=t-1-d_1[/math] оба чётны. Согласно принципу Дирихле, либо [math]|M|\geqslant p-1[/math], либо [math]N\geqslant q[/math]. Так как [math]|M|[/math] чётно, а [math]p-1[/math] нечётно, первое неравенство можно усилить, так что либо [math]|M|\geqslant p[/math], либо [math]|N|\geqslant q[/math].

Предположим [math]|M|\geqslant p=r(n-1,\;m)[/math]. Тогда либо подграф, порождённый множеством [math]M[/math], содержит белый [math]K_m[/math] и доказательство завершено, либо он содержит чёрный [math]K_{n-1}[/math], который вместе с вершиной 1 образует чёрный [math]K_n[/math]. Случай [math]|N|\geqslant q=r(n,\;m-1)[/math] рассматривается аналогично.
[math]\triangleleft[/math]
Утверждение (1):
Для натуральных чисел [math]m,n[/math] выполняется равенство [math]r(n,m) \le C_{n+m-2}^{n-1}[/math]
[math]\triangleright[/math]

Очевидно, [math]C^{n-1}_{n+m-2}=1[/math] при [math]n=1[/math] или [math]m=1[/math], как и соответствующие числа Рамсея. Индукцией по [math]n[/math] и [math]m[/math] при [math]n,m \ge 2[/math] получаем

[math]r(n,m) \le r(n,m-1)+r(n-1,m) \le C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}[/math]
[math]\triangleleft[/math]

С помощью неравенства из теоремы 1 можно получить несколько точных значений чисел Рамсея. Отметим что [math]r(3,3) \le 2r(2,3)=6[/math]. Так как числа [math]r(3,3)[/math] и [math]r(2,4)[/math] четны, можно вывести неравенства [math]r(3,4) \le r(3,3)+r(2,4)-1=9[/math]. И, наконец, [math]r(3,5) \le r(2,5)+r(3,4)=14[/math], а также [math]r(4,4) \le 2r(3,4)=18[/math]

Экстремальные примеры и оценки снизу

Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.

Определение:
Графом Рамсея [math]R(n,m)[/math] назовем такой граф на [math]r(n,m)-1[/math] вершинах, не содержащий ни клики на [math]n[/math] вершинах ни независимого множества на [math]m[/math] вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа [math]K_{r(m,n)-1}[/math], не содержащей ни клики на [math]n[/math] вершинах с рёбрами цвета 1 ни клики на [math]m[/math] вершинах с рёбрами цвета 2).

Граф [math]R(3,3)[/math] — это цикл на пяти вершинах. Экстремальный граф [math]R(3,4)[/math] — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы [math]R(3,5)[/math] и [math]R(4,4)[/math] имеют интересную числовую природу.

Так, если ассоциировать 13 вершин графа [math]R(3,5)[/math] с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 (то есть, 1, 5, 8 или 12).

Если считать 17 вершин графа [math]R(4,4)[/math] элементами поля вычетов по модулю 17, то рёбра будут соединять вычеты, разность которых — квадратичный вычет по модулю 17 (то есть, 1, 2, 4, 8, 9, 13, 15 или 16).

Существует гипотеза что любой граф [math]R(k,k)[/math] изоморфен своему дополнению(или что в раскраске полного графа на [math]r(k,k)-1[/math] вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.

Теорема (2):
Для любого натурального числа [math]k \ge 2[/math] выполняется неравенство [math]r(k,k) \ge k^{k/2}[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]R(2,2)=2[/math], достаточно рассмотреть случай [math]k \ge 3[/math]. Зафиксируем множество различных помеченных вершин [math]v_i,...,v_n[/math]. Пусть [math]g(n,k)[/math] — деля среди всех графов на вершинах [math]v_i,...,v_n[/math] тех графов, что содержат клику на [math]k[/math] вершинах. Всего графов на наших вершинах, очевидно [math]2^{C^2_n}[/math] (каждое из возможных [math]C^2_n[/math] можно провести или не провести).

Посчитаем графы с кликой на [math]k[/math] вершинах так: существует [math]C^k_n[/math] способов выбрать [math]k[/math] вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образом. Таким образом, каждый граф с кликой на [math]k[/math] вершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем [math]C^k_n\cdot 2^{C^2_n-C^2_k}[/math]. Следовательно,

[math]g(n,k) \le \frac{C^k_n}{2^{C^2_k}}\lt \frac{n^k}{k!\cdot 2^{C^2_k}}[/math] *

Подставив [math]n\lt 2^{k/2}[/math] в неравенство * мы получаем

[math]g(n,k)\lt \frac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}\lt \frac12[/math] при [math]k \ge 3[/math]

Предположим, что [math]r(k,k)=n\lt 2^{k/2}[/math] и разобьём все графы на n вершинах на пары [math]G, \overline G[/math] (граф и его дополнение) Так как [math]g(n,k)\lt \frac12[/math], то существует пара, в которой ни [math]G[/math], ни [math]\overline G[/math] не содержат клики на [math]k[/math] вершинах. Рассмотрим раскраску рёбер [math]K_n[/math] в два цвета, в которой ребра цвета 1 образуют граф [math]G[/math]. В такой раскраске нет клики на [math]k[/math] вершинах ни цвета 1, ни цвета 2, противоречие. Следовательно [math]r(k,k) \ge 2^{k/2}[/math].
[math]\triangleleft[/math]
Утверждение (2):
Для любых [math]k,m \in \mathbb N[/math] таких, что [math]2 \le k \le m[/math], выполняется неравенство [math]r(k,m) \ge 2^{k/2}[/math]

Числа Рамсея для раскрасок в несколько цветов

Определение:
Пусть [math]k,n_1,...,n_k \in \mathbb N[/math]. Число Рамсея [math]r(k;n_1,...,n_k)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что при любой раскраске рёбер полного графа на [math]x[/math] вершинах в [math]k[/math] цветов для некоторого [math]i \in [1..k][/math] обязательно найдётся клика на [math]n_i[/math] вершинах с рёбрами цвета [math]i[/math].


Утверждение (3):
Отметим, что [math]r(2;n,m)[/math] — это определённое ранее число Рамсея [math]r(n,m)[/math]

Обобщение оказывается настолько естественным что по сути не добавляет нам ничего нового: полностью аналогично теореме 1 и утверждению 1 можно доказать следующие факты.

Теорема (3):
Пусть [math]k,n_1,...,n_k \ge 2[/math] — натуральные числа. Тогда выполняются следующие утверждения:

[math]1) r(k;n_1,...,n_k) \le r(k;n_1-1,n_2,...,n_k)+r(k;n_1,n_2-1,...,n_k)++r(k;n_1,n_2,...,n_k-1)-k+2[/math]

[math]2)r(k;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ...\cdot n_k!}[/math]
Доказательство:
[math]\triangleright[/math]

1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 1

2) Доказательство аналогично утверждению 1. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел [math]n_1,...,n_k[/math] равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению:

[math]\frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ...\cdot n_k!}=\sum\limits_{i = 1}^k\frac{(n_1+...+(n_i-1)+...+n_k)!}{n_1!\cdot ...\cdot (n_i-1)!\cdot ...\cdot n_k!}[/math]

Следовательно, 2 неравенство из данной теоремы выводится из неравенства 1 по индукции.
[math]\triangleleft[/math]

Числа Рамсея больших размерностей

Определение:
Пусть [math]m,k,n_1,...,n_k \in \mathbb N[/math], причём [math]n_1,...,n_k \ge m[/math]. Число Рамсея [math]r_m(k; n_1,...,n_k)[/math] — наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что при любой раскраске [math]m[/math]-элементных подмножеств [math]x[/math]-элементного множества [math]M[/math] в [math]k[/math] цветов для некоторого [math]i \in [1..k][/math] обязательно найдётся такое множество [math]W_i[/math], что [math]|W_i|=n_i[/math] и все [math]m[/math]-элементные подмножества множества [math]W_i[/math] имеют цвет [math]i[/math].


Определение:
Число [math]m[/math] называется размерностью числа Рамсея [math]r_m(k;n_1,...,n_k)[/math].
Утверждение (4):
1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик
2) При количестве цветов, равном 2, этот параметр мы будем опускать и писать [math]r_m(n_1,n_2)[/math] вместо [math]r_m(2;n_1,n_2)[/math].
Определение:
Для каждою множества [math]M[/math] через [math]M^k[/math] мы будем обозначать множество всех [math]k[/math]-элементных подмножеств [math]M[/math].
Теорема (4):
Пусть [math]m,k,n_1,...,n_k[/math] — натуральные числа, причем [math]k \ge 2[/math], а [math]n_1,...,n_k \ge m[/math]. Тогда число Рамсея [math]r_m(k;n_1,...n_k)[/math] существует(то есть, конечно)
Доказательство:
[math]\triangleright[/math]

1)Мы будем доказывать теорему по индукции. Начнем со случая [math]k=2[/math]. Приступая к доказательству для числа [math]r_m(n_1,n_2)[/math] мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности [math]m[/math] с меньшей суммой [math]n_1+n_2[/math]. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что

[math]r_m(n_1,n_2)-1 \le p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))[/math]

Рассмотрим [math](p+1)[/math]-элементное множество [math]M[/math] и выделим в нём элемент [math]a[/math]. Пусть [math]M_0=M[/math]\{[math]a[/math]}. Пусть [math]\rho:M^m\rightarrow[/math] {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\rho': M_0^{m-1}\rightarrow[/math] {1,2}, определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\rho'(В) = \rho(B U[/math]{a}[math])[/math]. Так как [math]|M_0|=p[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_i \subset M_0[/math], для которого [math]\rho'(В)=1[/math] на всех [math]B \in M_1^{m-1}[/math], либо существует [math]r_m(n_1,n_2-1)[/math]-элементное подмножество [math]M_2 \subset M_0[/math], для которого [math]\rho'(B)=2[/math] на всех [math]B \in M_2^{m-1}[/math]. Случаи аналогичны, рассмотрим первый случай и множество [math]M_1[/math]. По индукционному предположен из [math]|M_1|=r_m(n_1-1,n_2)[/math] следует, что либо существует [math]n_1-1[/math]-элементное подмножество [math]N_1 \subset M_1[/math], для которого [math]\rho(A)=1[/math] на всех [math]A \in N^m_1[/math], либо существует [math]n_2[/math]-элементное подмножество [math]N_2 \subset M_1[/math], для которого [math]\rho(A)=2[/math] на всех [math]A \in N_2^m[/math]. Во втором случае искомое подмножество найдено (это [math]N_2[/math]), рассмотрим первый случай и множество [math]N=N_1 \cup [/math]{[math]a[/math]}. Пусть [math]A \in N^m[/math]. Если [math]A \not\ni a[/math], то [math]A \in N_1^m[/math] и следовательно [math]\rho(A)=1[/math]. Если же [math]A \ni a[/math], то множество [math]A[/math]\{[math]a[/math]}[math]\in N_1^{m-1} \subset M_1^{m-1}[/math] и поэтому [math]\rho(A)=\rho'(A[/math]\{[math]a[/math]}[math])=1[/math]. Учитывая, что [math]|N|=n_1[/math], мы нашли искомое подмножество и в этом случае.

2)При [math]k\gt 2[/math] будем вести индукцию по [math]k[/math] с доказанной выше базой [math]k=2[/math]. При [math]k\gt 2[/math] мы докажем неравенство

[math]r_m(k;n_1,...,n_k) \le q=r_m(r_m(k-1;n_1,...,n_{k-1}),n_k)[/math]

Для этого мы рассмотрим множество [math]M[/math] на [math]q[/math] вершинах и произвольную раскраску [math]\rho:M^m \rightarrow [1..k][/math] в [math]k[/math]цветов. Рассмотрим раскраску [math]\rho':M^m \rightarrow [/math]{[math]0,k[/math]}, в которой цвета [math]1,...,k-1[/math] раскраски [math]\rho[/math] склеены в цвет 0. Тогда существует либо таксе подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(k-1;n_1,...,n_{k-1})[/math] и [math]\rho'(A)=0[/math] на всех [math]A \in M_0^m[/math], либо существует такое [math]n_k[/math]-элементное подмножество [math]M_k \subset M[/math], что [math]\rho(A)=\rho'(A)=k[/math] на всех [math]A \in M^m_k[/math]. Во втором случае [math]M_k[/math] — искомое подмножество, а в первом случае заметим, что на любом подмножестве [math]A \in M_0^m[/math] из [math]\rho'(A)=0[/math] следует [math]\rho(A) \in [1..k-1][/math]. Исходя из размера множества [math]M_0[/math] по индукционному предположению получаем, что найдется искомое подмножество множества [math]M[/math] для одного из цветов [math]1,...,k-1[/math]
[math]\triangleleft[/math]

Числа Рамсея для произвольных графов

Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.

Определение:
Пусть [math]H_1,h_2[/math] — два данных графа. Число Рамсея [math]r(H_1,H_2)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что при любой раскраске рёбер полного графа на [math]x[/math] вершинах в два цвета обязательно найдется подграф, изоморфный [math]H_1[/math] с рёбрами цвета 1 или подграф изоморфный [math]H_2[/math] с рёбрами цвета 2

В принципе из результатов классической теории Рамсея понятие, что числа [math]r(H_1,H_2)[/math] обязательно существуют (то есть, конечны).

Лемма (1):
Пусть [math]m\gt 1[/math], а граф [math]H[/math] таков, что [math]v(H) \ge (m-1)(n-1)+1[/math] и [math]\alpha(H) \le m-1[/math]. Тогда граф [math]H[/math] содержит в качестве подграфа любое дерево на [math]n[/math] вершинах.
Доказательство:
[math]\triangleright[/math]

Зафиксируем [math]m[/math] и проведем индукцию по [math]n[/math]. База для [math]n=1[/math] очевидна. Докажем индукционный переход [math]n-1 \rightarrow n(n\gt 1[/math]. Рассмотрим произвольное дерево [math]T_n[/math] на [math]n[/math] вершинах, пусть дерево [math]T_{n-1}[/math] получено из [math]T_n[/math] удалением висячей вершины. Пусть [math]U[/math] — максимальное независимое множестве вершин графа [math]H[/math] Тогда [math]|U|=\alpha(H) \le m-1[/math], следовательно [math]v(H-U) \ge (m-1)(n-2)+1[/math] и очевидно [math]\alpha(H-U) \le m-1[/math].

По индукционному предположению, граф [math]H-U[/math] содержит в качестве подграфа дерево [math]T_{n-1}[/math]. Пусть [math]a[/math] — вершина этого дерева, присоединив к ксторой висячую вершину мы получим дерево [math]T_n[/math]. Заметим, что множество [math]U \cup[/math]{[math]a[/math]} не является независимым ввиду максимальности [math]U[/math]. Следовательно, вершина [math]a[/math] смежна хотя с одной вершиной [math]x \in U[/math]. Отметим, что [math]x \not\in V(T_{n-1})[/math] и, присоединив вершину [math]x[/math] к вершине [math]a[/math] дерева [math]T_{n-1}[/math], получим дерево [math]T_n[/math] в качестве подграфа графа [math]H[/math].
[math]\triangleleft[/math]
Теорема (5):
Пусть [math]T_n[/math] — дерево на [math]n[/math] вершинах. Тогда [math]r(T_n,K_m)=(m-1)(n-1)+1[/math].
Доказательство:
[math]\triangleright[/math]

1) Докажем, что [math]r(T_n,K_m) \ge (m-1)(n-1)+1[/math]. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на [math]n[/math] вершинах с рёбрами цвета 1 и нет клики на [math]m[/math] вершинах с рёбрами цвета 2. Разобьём вершины графа на [math]m-1[/math] клику по [math]n-1[/math] вершине и покрасим все рёбра этих клик в цвет 1. Тогда любой связный подграф с рёбрами цвета 1 содержит не более [math]n-1[/math] вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного [math]T_n[/math]. Рёбра цвета 2 (то есть, все оставшиеся рёбра) образуют [math](m-1)[/math]-дольный граф, в котором, очевидно, нет клики на [math]m[/math] вершинах.

2) Рассмотрим произвольную раскраску рёбер полного графа [math]K_{(m-1)(n-1)+1}[/math] в два цвета. Предположим, что не существует клики на [math]m[/math] вершинах с рёбрами цвета 2. Тогда [math]m\gt 1[/math] и [math]\alpha(G_1) \le m-1[/math]. По лемме 1, граф [math]G_1[/math] содержит в качестве подграфа любое дерево на [math]n[/math] вершинах в частности, дерево, изоморфное [math]T_n[/math].
[math]\triangleleft[/math]

Индуцированная теорема Рамсея

Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.

Определение:
Пусть [math]H[/math] — граф. Граф [math]G[/math] называется рамсеееским графом для [math]H[/math], если при любой раскраске рёбер графа [math]G[/math] в два цвета существует одноцветный по рёбрам индуцированный подграф графа [math]G[/math] изоморфный [math]H[/math]

При замене произвольного графа [math]H[/math] на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа [math]H[/math].

Теорема (6, Индуцированная теорема Рамсея):
Для любого графа существует рамсеевский граф

Случай двудольного графа

Здесь мы будем рассматривать двудольный граф [math]G[/math], как

[math]G=(V_1(G),V_2(G),E(G))[/math],

где [math]V_1(G)[/math] и [math]V_2(G)[/math] — разбиение множества вершин [math]V(G)[/math] на две доли, а рёбра соединяют вершины из разных долей.

Определение:
Пусть [math]H,G[/math] — двудольные графы. Инъективное отображение [math]\phi:V(H)\rightarrow V(G)[/math] назовём погружением, если оно удовлетворяет двум условиям.

1)[math]\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)[/math]
2)[math]\phi(u)\phi(v) \in E(G)[/math] тогда и только тогда когда [math]uv\in E(H)[/math]

В этом случае будем говорить, что двудольный граф [math]H[/math] погружён в двудольный граф [math]G[/math] и использовать обозначение [math]\phi(H)=G(\phi(V(H)))[/math]
Утверждение (5):
Отметим, что если существует погружение [math]\phi[/math] двудольного графа [math]H[/math] в двудольный граф [math]G[/math] то индуцированный подграф [math]\phi(H)[/math] графа [math]G[/math] изоморфен [math]H[/math]

Напомним, что для множества [math]X[/math] через [math]X^k[/math] мы обозначаем множество всех [math]k[/math]-элементных подмножеств множества [math]X[/math].

Определение:
Назовем особым двудольный граф вида [math]H=(V,V^k,E(H))[/math], где [math]E(H)=[/math]{[math]xY|x\in V,Y\in V^k, x\in Y[/math]}


Лемма (2):
Любой двудольный граф может быть погружен в особый двудольный граф.
Доказательство:
[math]\triangleright[/math]

Рассмотрим произвольный двудольный граф [math]P[/math], пусть [math]V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}[/math]. Положим [math]V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}[/math]

Построим погружение [math]P[/math] в особый двудольный граф [math]H=(V,V^{n+1},E)[/math].

Изначально положим [math]\phi(a_i)=x_i[/math]. Попробуем построить такое множество [math]Y_j\in V^{n+1}[/math], что [math]\phi(b_j)=Y_j[/math]. По определению погружения и множества [math]E(H)[/math], должно выполняться условие:
[math]Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)[/math]

Условие оставляет незаполненными [math]n+1-d_P(b_j)\ge 1[/math] элементов множества [math]Y_j[/math] (единственное ограничение эти элементы не могут быть вершинами [math]x_1,...,x_n[/math]). Поместим в [math]Y_j[/math] элемент-индекс [math]z_j[/math] (чтобы [math]Y_j\not=Y_l[/math] при [math]j \not=l[/math], и дополним произвольно элементами из [math]y_1,...,y_n[/math], чтобы в множестве [math]Y_j[/math] было ровно [math]n+1[/math] элементов.
[math]\triangleleft[/math]
Лемма (3):
Для любого двудольного графа [math]H[/math] существует такой двудольный граф [math]G[/math], что для любой раскраски рёбер [math]G[/math] в два цвета обязательно существует погружение [math]\phi[/math] графа [math]H[/math] в граф [math]G[/math] в котором все рёбра [math]\phi(H)[/math] одноцветны.
Доказательство:
[math]\triangleright[/math]
Утверждение (6):
Разумеется, указанный в условии леммы 3 граф [math]G[/math] будет рамсеевским графом для [math]H[/math]. Утверждение леммы более сильное: мы дополнительно требуем, чтобы все вершины одной доли [math]H[/math] можно было погрузить в одну долю графа [math]G[/math].

Ввиду леммы 2 достаточно доказать утверждение для особого двудольного графа [math]H=(V,V^k,E(H))[/math]. Пусть [math]|V|=n[/math]. Докажем что рамсеевским графом для [math]H[/math] будет особый двудольный граф [math]G=(U,U^{2k-1},E(G))[/math], где
[math]|U|=r_{2k-1}(2C^k_{2k-1};kn+k-1,...,kn+k-1).[/math] **
Рассмотрим произвольную раскраску рёбер графа [math]G[/math] в два цвета 1 и 2. Каждое множество [math]Y\in U^{2k-1}[/math] смежно как вершина особого двудольного графа [math]G[/math] с [math]2k-1[/math] вершиной, хотя бы [math]k[/math] из этих рёбер имеет одинаковый цвет. Выберем и зафиксируем для каждого множества [math]Y[/math] его подмножество [math]S(Y)[/math], состоящее из [math]k[/math] вершин доли [math]U[/math] соединённых с [math]Y[/math] рёбрами одинакового цвета. Пусть [math]c(Y)\in \{1,2\}[/math] — это цвет рёбер соединяющий [math]Y[/math] с вершинами из [math]S(Y)[/math].

Можно считать, что элементы [math]U[/math] упорядочены. Тогда элементы каждого множества [math]Y\in U^{2k-1}[/math] будут упорядочены. Обозначим через [math]\sigma(Y)[/math] множество номеров [math]k[/math] элементов множества [math]S(Y)[/math] в порядке элементов множества [math]Y[/math]. Тогда [math]\sigma(Y)[/math] может принимать ровно [math]C^k_{2k-1}[/math] значений.

Покрасим множество [math]U^{2k-1}[/math] (то есть все [math](2k-1)[/math]-элементные подмножества [math]U[/math]) в [math]2C^k_{2k-1}[/math]цветов: цветом подмножества [math]Y[/math] будет пара [math](\sigma(Y),c(Y))[/math]. Из выбора размера множества [math]U[/math] (см. условие **) следует, что ceotcndetn такое подмножество [math]W\subset U[/math], что [math]|W|=kn+k-1[/math] и все подмножества [math]Y\subset W^{2k-1}[/math] имеют одинаковый цвет [math](\sigma(Y),c(Y))[/math] (не умаляя общности будем считать, что [math]\sigma(Y)=\sigma, c(Y)=1)[/math]. Мы найдём погружение графа [math]H[/math] в [math]G(W)[/math], все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.

Занумеруем элементы множества [math]W[/math] в порядке их следования в [math]U[/math]: пусть [math]W=\{w_1,...,w_{kn+k-1}\}[/math]. Введем обозначения

[math]t_j=w_kj, T=\{t_1,...,t_n\}, V=\{a_1,...,a_n\}[/math].

Положим [math]\phi(a_i)=t_i[/math]. Остаётся корректно определить [math]\phi(Z)[/math] для каждого множества [math]Z\in V^k[/math]. Прежде чем построить [math]\phi(Z)=Y\in U^{2k-1}[/math] мы положим [math]S(Y)=\{\phi(x):x\in Z\}[/math]. Из определения погружения понятно, что тогда должно выполняться условие [math]S(Y)=Y\cap T[/math], а следовательно, нам нужно дополнить множество [math]Y[/math] еще [math]k-1[/math] элементами, не входящими в множество [math]T[/math]. Мы сделаем это так, чтобы множество порядков номеров элементов множества [math]S(Y)[/math] среди элементов множества [math]Y[/math] было [math]\sigma(Y)=\sigma[/math]: так как [math]t_i=w_ki[/math], не входящих в [math]T[/math] элементов [math]W[/math] хватит, чтобы обеспечить это.

Так как по выбору множества [math]W[/math] мы имеем [math]\sigma(Y)=\sigma[/math], множество [math]S(Y)[/math] выбрано корректно и, опять же в силу выбора [math]W[/math], все рёбра особого двудольного графа [math]G[/math] между вершинами из [math]S(Y)=\{\phi(x):x\in Z\}[/math] и [math]Y=\phi(Z)[/math] покрашены в цвет 1. В завершение остается лишь добавить, что при [math]Z\not=Z'[/math] мы по построению имеем [math]S(\phi(Z))\not=S(\phi(Z'))[/math], поэтому [math]\phi(Z)\not=\phi(Z')[/math]. Таким образом искомое погружение построено.
[math]\triangleleft[/math]

Случай произвольного графа

Теорема (7):
Для произвольного графа [math]H[/math] существует рамсеевский граф.
Доказательство:
[math]\triangleright[/math]

Пусть [math]k=v(H),n=r(k,k)[/math]. Пронумеруем вершины графа [math]H[/math]. Построим граф [math]G^0[/math] следующим образом: разместим его вершины в виде таблице [math]n \times C^k_n[/math]. Таким образом в каждом столбце вершины окажутся пронумерованы числами от 1 до [math]n[/math], как соответствующие строки таблицы. В каждом столбце одним из [math]C^k_n[/math] способов разместим граф [math]H[/math] (каждый столбец соответствует одному из возможных способов размещения). Все рёбра графа [math]G^0[/math] будут рёбрами указанных копий графа [math]H[/math].

Граф [math]G^0[/math] является [math]n[/math]-дольным, его естественное разбиение на доли задаётся таблицей: [math]V_i(G^0)[/math] — это вершины, соответствующие [math]i[/math] ряду таблицы. Мы последовательно в несколько шагов будем перестраивать наш граф с помощью леммы 3, так, чтобы вершины последующих графов также разбивались на [math]n[/math] долей и записывались в виде таблицы. Каждый шаг будет соответствовать одной паре строк таблицы.

Шаг перестройки графа.

Итак, пусть мы имеем [math]n[/math]-дольный граф [math]G^l[/math], доли которого [math]V_i=V_i(G^l)[/math] (где [math]i\in [1..n][/math]). Пусть с парой строк (и, соответственно, долей) [math]i,j[/math] мы еще не выполняли шаг. Очевидно, граф [math]G_{i,j}=G^l(V_i\cup V_j)[/math] двудолен и для него по лемме 3 существует двудольный рамсеевский граф [math]P_{i,j}[/math]. Более того если вершины [math]P_{i,j}[/math] разбиты на две доли [math]W_i[/math] и [math]W_j[/math], то для любой раскраски рёбер в два цвета существует одноцветное погружение [math]\phi[/math] графа [math]G_{i,j}[/math] в [math]P_{i,j}[/math] в котором [math]\phi(V_i)\subset W_i[/math] и [math]\phi(V_j)\subset W_j[/math]. Назовём таксе погружение одноцветным.

Перейдём к построению [math]G^{l+1}[/math]. Заменим [math]V_i[/math] на [math]W_i[/math] и [math]V_j[/math] на [math]W_j[/math], проведем между этими долями все рёбра графа [math]P_{i,j}[/math]. Наша цель в том, чтобы для любого погружения [math]G_{i,j}[/math] в [math]P_{i,j}[/math] была содержащая его копия [math]G^l[/math] (причем доли этой копии лежали в соответствующих строках таблицы графа [math]G^{l+1}[/math]

Занумеруем всевозможные погружения [math]G_{i,j}[/math] в [math]P_{i,j}[/math]: пусть это [math]G_{i,j}(1),...,G_{i,j}(q)[/math]. Каждому погружению [math]G_{i,j}(s)[/math] мы поставим в соответствие отдельные копии всех отличных от [math]V_i[/math] и [math]V_j[/math] долей: [math]V_1(s),...,V_n(s)[/math]. Положим [math]V_i(s)=V(G_{i,j}(s))\cap W_i[/math] и [math]V_j(s)=V(G_{i,j}(s))\cap W_j[/math]. На этих долях построим копию графа [math]G^l[/math]. В результате для каждого погружения графа [math]G_{i,j}[/math] в [math]P_{i,j}[/math] мы построили свою копию графа [math]G^l[/math].

Выделение одноцветного индуцированного подграфа.

Итак, докажем, что [math]G=G^{C^2_n}[/math] и есть рамсеевский граф для [math]H[/math]. Пусть [math]p_1,...,p_{C^2_n}[/math] — именно такая нумерация пар строк в нашей таблице, в порядке которой совершались шаги перестройки графа. Рассмотрим произвольную раскраску рёбер [math]\rho[/math] графа [math]G[/math] в два цвета и докажем следующий факт.

Утверждение (7):
Для каждого [math]l\in [0..C^2_n][/math] существует изоморфный [math]G^l[/math] индуцированный подграф графа [math]G[/math], в котором для пар строк [math]p_{l+1},...,p_{C^2_n}[/math] все рёбра между вершинами соответствующих пар строк в раскраске [math]\rho[/math] одноцветны.
[math]\triangleright[/math]

Индукция с обратным ходом от [math]l=C^2_n[/math] к [math]l=0[/math]. База для [math]l=C^2_n[/math] очевидна. Докажем переход [math]l\rightarrow l-1[/math]

Итак рассмотрим наш изоморфный [math]G^l[/math] подграф, который мы для простоты будем обозначать [math]G^l[/math] и пару строку [math]p_l[/math] в нем: пусть это строки [math]i[/math] и [math]j[/math], a [math]P_{i,j}[/math] и [math]G_{i,j}[/math] — те двудольные графы между этими строками, что описаны в шаге построения. Так как [math]P_{i,j}[/math] (подграф графа [math]G^l[/math]) — рамсеевский граф для [math]G_{i,j}[/math], мы можем выбрать одноцветное в раскраске [math]\rho[/math] погружение [math]G_{i,j}[/math] в [math]P_{i,j}[/math] и соответствующая ему по построению копия [math]G^{l-1}[/math] будет искомым (из построения очевидно, что индуцированным!) подграфом [math]G^l[/math] а значит, и [math]G[/math]
[math]\triangleleft[/math]
Таким образом, существует изоморфный [math]G^0[/math] индуцированный под­граф графа [math]G[/math], в котором для каждой пары строк [math]i,j[/math] все ребра между вершинами соответствующих строк одноцветны в раскраске [math]\rho[/math]. Будем обозначать этот граф просто [math]G^0[/math]. Рассмотрим граф [math]K_n[/math], вершины которого соответствуют строкам таблицы и покрасим каждое ребро в цвет, в который покрашены рёбра [math]G^0[/math] между соответствующими строками. Так как [math]n=r(k,k)[/math], существуют [math]k[/math] вершин, между которыми все рёбра одноцветны. Рассмотрим столбец графа [math]G^0[/math], в котором [math]H[/math] размещён именно в строчках, соответствующих этим [math]k[/math] вершинам. Подграф [math]H'[/math] графа [math]G^0[/math] на вершинах этого столбца и соответствующих строчках изоморфен [math]H[/math], по построению является индуцированным подграфом графа [math]G^0[/math] и все его рёбра одноцветны в раскраске [math]\rho[/math]. Остаётся лишь заметить, что [math]H'[/math] — индуцированный подграф графа [math]G[/math].
[math]\triangleleft[/math]

См. также

Источники информации