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

Эта статья находится в разработке!

Числа Рамсея

Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на [math]n[/math] вершинах будем называть кликой.

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

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

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

Теорема (P. Erdos, G. Szekeres):

Пусть [math]n,m \ge 2[/math]-натуральные числа. Тогда [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]\triangleright[/math]

1) Рассмотрим клику на [math]r(n, m - 1) + r(n - 1, m)[/math] вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину [math]a[/math]. Тогда либо от вершины [math]a[/math] отходит хотя бы [math]r(n, m - 1)[/math] рёбер цвета 2, либо от вершины [math]a[/math] отходит хотя бы [math]r(n—1, m)[/math] рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на [math]r(n, m — 1)[/math] вершинах, соединенных с [math]a[/math] рёбрами цвета 2. На этих вершинах есть либо клика на [math]n[/math] вершинах с ребрами цвета 1, либо клика на [math]m—1[/math] вершинах с рёбрами цвета 2. Во втором случае добавим вершину [math]a[/math] и получим клику на [math]m[/math] вершинах с рёбрами цвета 2. Теперь из определения [math]r(n, m)[/math] следует неравенство. 2) Рассмотрим клику на [math]r(n, m-l)+r(n-1, m)-1[/math] вершинах с рёбрами цветов 1 и 2 и его произвольную вершину [math]a[/math]. Если вершине [math]a[/math] инцидентны хотя бы [math]r(n,m-1)[/math] рёбер цвета 2 или хотя бы [math]r(n-1,m)[/math] рёбер цвета 1, то мы найдём в графе клику на [math]n[/math] вершинах с рёбрами цвета 1 или клику на [math]m[/math] вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине [math]a[/math] инцидентны ровно [math]r(n, m-1)-1[/math] рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего [math]r(n, m-1)+r(n-1, m)-1[/math] вершин и степень каждой вершины равна [math]r(n, m-1)-1[/math]. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда [math]r(n, m-1)[/math] и [math]r(n-1,m)[/math] — чётные, выполняется неравенство [math](n, m)\lt r(n, m-1)+r(n-1, 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]

С помощью неравенства из теоремы можно получить несколько точных значений чисел Рамсея. Отметим что [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). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.

Теорема (P. Erdos):

Для любого натурального числа [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*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!*2^{C^2_k}}[/math] Подставив [math]n\lt 2^{k/2}[/math] в неравенстве мы получаем [math]g(n,k)\lt \frac{2^{k^2/2}*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].

Утверждение:

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

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

Теорема:

Пусть [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!*n_2!*...*n_k!}[/math]

Доказательство:

[math]\triangleright[/math]

1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 2) Доказательство аналогично следствию 1. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел [math]n_1,...,n_k[/math] равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: [math]\frac{(n_1+n_2+...+n_k)!}{n_1!*n_2!*...*n_k!}=\sum\limits_{i = 1}^k\frac{(n_1+...+(n_i-1)+...+n_k)!}{n_1!*...*(n_i-1)!*...*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].

Утверждение:

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].

Теорема:

Пусть [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]\alpha:M^m\rightarrow[/math] {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\alpha': M_0^{m-1}\rightarrow[/math] {1,2}, определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\alpha'(В) = \alpha(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]\alpha'(В)=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]\alpha'(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]\alpha(A)=1[/math] на всех [math]A \in N^m_1[/math], либо существует [math]n_2[/math]-элементное подмножество [math]N_2 \subset M_1[/math], для которого [math]\alpha(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]\alpha(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]\alpha(A)=\alpha'(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]\alpha:M^m \rightarrow [1..k][/math] в [math]k[/math]цветов. Рассмотрим раскраску [math]\alpha':M^m \rightarrow [/math]{[math]0,k[/math]}, в которой цвета [math]1,...,k-1[/math] раскраски [math]\alpha[/math] склеены в цвет 0. Тогда существует либо таксе подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(k-1;n_1,...,n_{k-1})[/math] и [math]\alpha'(A)=0[/math] на всех [math]A \in M_0^m[/math], либо существует такое [math]n_k[/math]-элементное подмножество [math]M_k \subset M[/math], что [math]\alpha(A)=\alpha'(A)=k[/math] на всех [math]A \in M^m_k[/math]. Во втором случае [math]M_k[/math] — искомое подмножество, а в первом случае заметим, что на любом подмножестве [math]A \in M_0^m[/math] из [math]\alpha'(A)=0[/math] следует [math]\alpha(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] обязательно существуют (то есть, конечны).

Лемма:

Пусть [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]

Теорема (V. Chvatal):

Пусть [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]. По лемме, граф [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].

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

Для любого графа существует рамсеевский граф

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

Здесь мы будем рассматривать двудольный граф [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]

Утверждение:

Отметим, что если существует погружение [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]}

Лемма:

Любой двудольный граф может быть погружен в особый двудольный граф.

Доказательство:

[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]

Лемма:

Для любого двудольного графа [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]

Утверждение: Разумеется, указанный е уел сени леммы 1С.З граф G будет рамсееЕСким графем для Я. Утверждение леммы белее сильное: мы дополнительно требуем, чтобы ьсе вершины одной дели Я можно было погрузить в одну долю графа G. Ввиду леммы достаточно доказать утверждение для особого двудольного графа [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]

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

Теорема 1С.6. Для щствольного графа Н существует рамсеевский граф, Доказательство. Пусть к — v(H), п — г(к,к). Пронумеруем Еершины графа Н. Построим граф G0 следующим образсм: разместим его верши­ны е виде таблице п х Ск. Таким образом в каждом столбце Еершины окажутся пронумерованы числами ст 1 до п. как соответствующие стро­ки таблицы. Е каждом столбце одним из Ск способов разместим граф Н (каждый столбец соответствует одному из возможных споссбсЕ разме­щения). Все рёбра графа G0 будут рёбрами указанных копий графа Н, Граф G0 является п-дсльным, егс естественное разбиение на доли задаётся таблицей: V^(G°) — это вершины, соответствующие г ряду таб­лицы. Мы последовательно е несколько шагов будем нерестраивать наш граф с помощью леммы 1С.З так. чтобы вершины последующих графов также разбивались на п долей и записывались в виде таблицы. Каждый шаг будет состЕСтстЕСвать однсй паре строк таблицы, Шаг перестройки графа. Итак, пусть мы имеем n-дольный граф Ge, доли которого К = К(Сг) (где г 6 [1--п]) Пусть с парой строк (и. соответственно, долей) i,j мы еше не выполняли шаг. Очеьидно, граф Gitj = Gt{Vi\JVj) дЕудолен и для него не лемме 10.3 сушестЕует двудольный рамсееЕОкий граф Pitj. Еолее того если вершины Р^- разбиты на дес доли Wi и Wj. тс для любой раскраски рёбер в два цЕета существует одвснветнсе Есгружение (р графа Gitj е Pitj в котором (p(Vj) С Wi и ip(Vj) С Wj Назовём таксе погружение одноцветным. Перейдём к построению Ge+1. Заменим К на Wi и Vj на Wj. прове­дём между зтими долями Есе рёбра графа Pitj. Наша цель в тем, чтобы для любого погружения Gitj в Р^ была содержащая его кспия Ge (при­чём доли этой копии лежали в соответствующих строках таблицы графа

занумеруем всевозможные погружения Gij в Pitj: пусть это Gjj(l),... Gij{q). Каждому погружению Gitj(s) мы поставим в соответствие отдель­ные кспии Есех отличных ст Vj, и Vj долей: Vi(s),..., Vn(s). Положим Vi(s) = V(Gij(s))nWi и Vj(s) = V(Gij(s))r\Wj. На зтих долях построим копию графа Ge В результате для каждого погружения графа Gitj в Pitj мы построили свею копию графа Ge. Выделение одноцветного индуцированного подграфа. Итак, докажем, что G = Gc" и есть рамсеевский граф для Н. Пусть Ри - ■ ■ iPci — именно такая нумерация пар строк в нашей таблице, ь по­рядке которой совершались шаги перестройки графа. Еассмстрим про­извольную раскраску рёбер р графа G ь два цвета и докажем следующий факт. Для каждссс £ е [0..С2] существует изоморфные G1 иьсуьирсван- ный поограф графа G. б котором для пар строк ре+г- .., рс% все рёбра между вершинами ссответстеукших пар строк в раскраске р одно­цветны Доказательство. Индукция с обратным ходом ст £ — С2п к £ — 0. База для £ = С\ очеЕидна. Докажем переход £ ^ £ — 1 Итак рассмотрим наш изоморфный G1 подграф который мы для простоты будем обозначать Ge и пару строку е нем пусть это строки г и j. a Pij и Gitj — те двудольные графы между этими строками, что спи­саны в шаге псстроения. Так как Pjj (подграф графа Ge) — рамссеЕСкий граф для Gij. мы межем выбрать одноцветное е раскраске р погружение Gij в Pitj и соответствующая ему по построению копия Ge_1 будет иско­мым (из построения очевидно, чте индуиирсьанным!) подграфом Ge а значит, bG □ Таким образом, сушестнует иземерфный G0 индуцированный под­граф графа G. е кстсрем для каждой пары стрск i,j Есе ребра меж­ду Есршинами состЕСтстЕуюших строк одноцветны е раскраске р. Будем обозначать зтот граф просто G0. Бассмстрим граф Кп Еершины кото­рого соответствуют строкам таблицы и искрасим каждое ребро в пест в который покрашены рёбра G0 между соответствующими строками Так как п = r(k,k) существуют к Есршин, между которыми ьсе рёбра одно­цветны. Рассмотрим столбец графа G°, е котором Н размещён именно е строчках. соответствующих этим к вершинам. Подграф Н' графа G0 на вершинах этого столбца и соответствующих строчках из с мор фен Н пс построению является индугшрсЕанным подграфом графа G0 и все его рёбра одноцветны в раскраске р. Остаётся лишь заметить, что Я' — ин­дуцированный подграф графа G. □