Теория Рамсея

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

Числа Рамсея

Определение:

Кликой в неориентированном графе [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]

См. также

• Раскраска графа
• Раскраска двудольного графа в два цвета
• Теорема Турана об экстремальном графе

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

• Wikipedia — Ramsey's theorem
• Wikipedia — Ramsey theory
• An Introduction to Ramsey Theory on Graphs
• Ramsey Theory