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

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

Числа Рамсея

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

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

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

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

Раскраска [math]K_5[/math] без одноцветных треугольников

Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах". Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы [math]m[/math] человек были попарно знакомы, или хотя бы [math]n[/math] человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея [math]r(m, n)[/math], представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что [math]r(3,3) = 6[/math]. Представим, что ребра [math]K_6[/math] раскрашены в два цвета: красный и синий. Возьмем вершину [math]v[/math]. Данной вершине, как и всем другим, инцидентны [math]5[/math] рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы [math]3[/math] ребра, соединяющие вершину [math]v[/math] с вершинами [math]r[/math], [math]s[/math], [math]t[/math], синие. Если хотя бы одно из ребер [math]rs[/math], [math]rt[/math], [math]st[/math] синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, [math]r(3,3) \le 6 [/math]. Чтобы доказать, что [math]r(3,3) = 6 [/math], предъявим такую раскраску графа [math]K_5[/math], где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

Теорема Рамсея. Оценки сверху

Теорема (1, Теорема Рамсея):

Для любых [math]n,m \in \mathbb N[/math] существует число [math]r(n,m)[/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]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], так как граф, состоящий из одной вершины, можно считать полным графом любого цвета. Индукционный переход: Пусть [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]s=p+q-1[/math] и рассмотрим чёрно-белый граф из [math]s[/math] вершин. Если [math]d_i[/math] степень [math]i[/math]-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, [math]\sum_{i=1}^s d_i[/math] — чётно. Поскольку [math]s[/math] нечётно, должно существовать чётное [math]d_i[/math]. Не умаляя общности, положим, что [math]d_1[/math] чётно. Обозначим через [math]M[/math] и [math]N[/math] вершины инцидентные вершине [math]1[/math] в чёрном и белом подграфах соответственно. Тогда [math]|M|=d_1[/math] и [math]|N|=s-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], который вместе с вершиной [math]1[/math] образует чёрный [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]

Оценки снизу

Теорема (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,\ldots,v_n[/math]. Пусть [math]g(n,k)[/math] — доля среди всех графов на вершинах [math]v_i,\ldots,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 \dfrac{C^k_n}{2^{C^2_k}}\lt \dfrac{n^k}{k!\cdot 2^{C^2_k}}[/math] [math](*)[/math] Подставив [math]n\lt 2^{k/2}[/math] в неравенство [math](*)[/math] мы получаем [math]g(n,k)\lt \dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}\lt \dfrac12[/math] при [math]k \ge 3[/math] Предположим, что [math]r(k,k)=n\lt 2^{k/2}[/math] и разобьём все графы на [math]n[/math] вершинах на пары [math]G, \overline G[/math] (граф и его дополнение) Так как [math]g(n,k)\lt \dfrac12[/math], то существует пара, в которой ни [math]G[/math], ни [math]\overline G[/math] не содержат клики на [math]k[/math] вершинах. Рассмотрим раскраску рёбер [math]K_n[/math] в два цвета, в которой ребра цвета [math]1[/math] образуют граф [math]G[/math]. В такой раскраске нет клики на [math]k[/math] вершинах ни цвета [math]1[/math], ни цвета [math]1[/math], получили противоречи противоречие. Значит [math]n[/math] было выбрано неверно. Из этого следует [math]r(k,k) \ge 2^{k/2}[/math].

[math]\triangleleft[/math]

Свойства чисел Рамсея

Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея [math]r(n,m)[/math] на практике.

• [math]r(n,m) = r(m,n)[/math]
• [math]r(1,m) = 1[/math]
• [math]r(2,m) = m[/math]

Значения чисел Рамсея

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

Числа Рамсея
[math]n,\ m[/math]	[math]1 [/math]	[math]2 [/math]	[math]3 [/math]	[math]4 [/math]	[math]5 [/math]	[math]6 [/math]	[math]7 [/math]	[math]8 [/math]	[math]9 [/math]	[math]10[/math]
[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]	[math]1 [/math]
[math]2 [/math]	[math]1 [/math]	[math]2 [/math]	[math]3 [/math]	[math]4 [/math]	[math]5 [/math]	[math]6 [/math]	[math]7 [/math]	[math]8 [/math]	[math]9 [/math]	[math]10[/math]
[math]3[/math]	[math]1[/math]	[math]3[/math]	[math]6[/math]	[math]9[/math]	[math]14[/math]	[math]18[/math]	[math]23[/math]	[math]28[/math]	[math]36[/math]	[math][40, 42][/math]
[math]4[/math]	[math]1[/math]	[math]4[/math]	[math]9[/math]	[math]18[/math]	[math]25[/math]	[math][36, 41][/math]	[math][49, 61][/math]	[math][59, 84][/math]	[math][73, 115][/math]	[math][92, 149][/math]
[math]5[/math]	[math]1[/math]	[math]5[/math]	[math]14[/math]	[math]25[/math]	[math][43, 48][/math]	[math][58, 87][/math]	[math][80, 143][/math]	[math][101, 216][/math]	[math][133, 316][/math]	[math][149, 442][/math]
[math]6[/math]	[math]1[/math]	[math]6[/math]	[math]18[/math]	[math][36, 41][/math]	[math][58, 87][/math]	[math][102, 165][/math]	[math][115, 298][/math]	[math][134, 495][/math]	[math][183, 780][/math]	[math][204, 1171][/math]
[math]7[/math]	[math]1[/math]	[math]7[/math]	[math]23[/math]	[math][49, 61][/math]	[math][80, 143][/math]	[math][115, 298][/math]	[math][205, 540][/math]	[math][217, 1031][/math]	[math][252, 1713][/math]	[math][292, 2826][/math]
[math]8[/math]	[math]1[/math]	[math]8[/math]	[math]28[/math]	[math][56, 84][/math]	[math][101, 216][/math]	[math][127, 495][/math]	[math][217, 1031][/math]	[math][282, 1870][/math]	[math][329, 3583][/math]	[math][343, 6090][/math]
[math]9[/math]	[math]1[/math]	[math]9[/math]	[math]36[/math]	[math][73, 115][/math]	[math][133, 316][/math]	[math][183, 780][/math]	[math][252, 1713][/math]	[math][329, 3583][/math]	[math][565, 6588][/math]	[math][580, 12677][/math]
[math]10[/math]	[math]1[/math]	[math]10[/math]	[math][40, 42][/math]	[math][92, 149][/math]	[math][149, 442][/math]	[math][179, 1171][/math]	[math][289, 2826][/math]	[math][343, 6090][/math]	[math][581, 12677][/math]	[math][798, 23556][/math]

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

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

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

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

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

Теорема (3):

Пусть [math]k,n_1,\ldots,n_k \ge 2[/math] — натуральные числа. Тогда выполняются следующие утверждения: [math]1) r(k;n_1,\ldots,n_k) \le r(k;n_1-1,n_2,\ldots,n_k)+r(k;n_1,n_2-1,\ldots,n_k)++r(k;n_1,n_2,\ldots,n_k-1)-k+2[/math] [math]2)r(k;n_1,\ldots,n_k) \le \frac{(n_1+n_2+\ldots+n_k)!}{n_1!\cdot n_2!\cdot \ldots\cdot n_k!}[/math]

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

Пусть [math]m,k,n_1,\ldots ,n_k \in \mathbb N[/math], причём [math]n_1,\ldots ,n_k \ge m[/math]. Число Рамсея [math]r_m(k; n_1,\ldots ,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\ldots 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,\ldots ,n_k)[/math].

Нетрудно понять что числа Рамсея размерности [math]2[/math] — это определённые ранее числа Рамсея для клик.

При количестве цветов, равном [math]2[/math], этот параметр в записи обычно опускают и пишут [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,\ldots,n_k[/math] — натуральные числа, причем [math]k \ge 2[/math], а [math]n_1,\ldots ,n_k \ge m[/math]. Тогда число Рамсея [math]r_m(k;n_1,\ldots 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,\ldots ,n_k) \le q=r_m(r_m(k-1;n_1,\ldots ,n_{k-1}),n_k)[/math] Для этого мы рассмотрим множество [math]M[/math] на [math]q[/math] вершинах и произвольную раскраску [math]\rho:M^m \rightarrow [1 \ldots k][/math] в [math]k[/math]цветов. Рассмотрим раскраску [math]\rho':M^m \rightarrow [/math]{[math]0,k[/math]}, в которой цвета [math]1,\ldots,k-1[/math] раскраски [math]\rho[/math] склеены в цвет 0. Тогда существует либо таксе подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(k-1;n_1,\ldots ,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 \ldots k-1][/math]. Исходя из размера множества [math]M_0[/math] по индукционному предположению получаем, что найдется искомое подмножество множества [math]M[/math] для одного из цветов [math]1,\ldots ,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] с рёбрами цвета [math]1[/math] или подграф изоморфный [math]H_2[/math] с рёбрами цвета [math]2[/math].

Из результатов классической теории Рамсея становится понятно, что числа [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[/math], докажем для [math]n[/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]r(T_n,K_m)=(m-1)(n-1)+1[/math], где [math]T_n[/math] — дерево на [math]n[/math] вершинах.

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

[math]\triangleright[/math]

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

См. также

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

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

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