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

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

Числа Рамсея

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

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

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

Число Рамсея [math]r(n, m)[/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]r(n, m)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что для любого графа [math]G[/math] на [math]x[/math] вершинах либо в [math]G[/math] найдется [math]K_n[/math], либо в [math]\overline G[/math] найдется граф [math]K_m[/math].

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

Несложно доказать, что данные определения эквивалентны. Достаточно показать, что раскрашенному в два цвета графу [math]K_n[/math], можно однозначно поставить в соответствие граф [math]G[/math] на [math]n[/math] вершинах. Довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах". Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы [math]n[/math] человек были попарно знакомы, или хотя бы [math]m[/math] человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея [math]r(n, m)[/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) \leqslant 6 [/math]. Чтобы доказать, что [math]r(3,3) = 6 [/math], предъявим такую раскраску графа [math]K_5[/math], где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для [math] K_4[/math], [math]K_3[/math] не нужно, так как достаточно взять соответствующие подграфы раскрашенного [math]K_5[/math].

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

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

Для любых [math]n,m \in \mathbb N[/math] существует число [math]r(n,m)[/math], при этом [math]r(n,m) \leqslant 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) \leqslant r(n,m-1)+r(n-1,m) - 1[/math] .

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

[math]\triangleright[/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]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\limits_{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]r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1[/math].

[math]\triangleleft[/math]

Утверждение (1):

Для натуральных чисел [math]m,n[/math] выполняется равенство [math]r(n,m) \leqslant 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 \geqslant 2[/math] получаем [math]r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant 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 \geqslant 2[/math] выполняется неравенство [math]r(k,k) \geqslant 2^{k/2}[/math]

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

[math]\triangleright[/math]

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

Теорема (3,Теорема Рамсея для нескольких цветов):

[math]\forall k, n_1, \ldots n_k \in \mathbb N [/math] существует число Рамсея [math]r(n_1,\ldots,n_k)[/math], при этом [math]r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).[/math]

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

[math]\triangleright[/math]

Возьмем граф из [math]r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))[/math] вершин и окрасим его рёбра в [math]k[/math] цветов. Пока что будем считать цвета [math]k-1[/math] и [math]k[/math] одним цветом. Тогда граф будет [math](k-1)[/math]-цветным. Согласно определению числа Рамсея [math]r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))[/math], такой граф либо содержит [math]K_{n_i}[/math] для некоторого цвета [math]i[/math], такого что [math]1\leqslant i\leqslant k-2[/math], либо [math]K_{r(n_{k-1},n_k)}[/math], окрашенный общим цветом [math]k-1[/math] и [math]k[/math]. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный [math]r(n_{k-1},n_k)[/math] — вершинный граф содержит либо [math]K_{n_{k-1}}[/math] цвета [math]k-1[/math], либо [math]K_{n_k}[/math] цвета [math]k[/math]. Таким образом любое число Рамсея для раскраски в [math]k[/math] цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, [math]r(n_1,\ldots,n_k)[/math] существует для любых [math] k, n_1, \ldots n_k, \in \mathbb N [/math], и теорема доказана.

[math]\triangleleft[/math]

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

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

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

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

Теорема (4, Теорема Рамсея для чисел больших размерностей):

Пусть [math]m,k,n_1,\ldots,n_k[/math] — натуральные числа, причем [math]k \geqslant 2[/math], а [math]n_1,\ldots ,n_k \geqslant m[/math]. Тогда существует число Рамсея [math]r_m(n_1,\ldots n_k)[/math].

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

[math]\triangleright[/math]

Мы будем доказывать теорему по индукции. Начнем со случая [math]k=2[/math]. Приступая к доказательству для числа [math]r_m(n_1,n_2)[/math] мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности [math]m[/math] с меньшей суммой [math]n_1+n_2[/math]. В качестве базы будем использовать случай чисел Рамсея размерности [math]2[/math] разобранный выше. Итак, мы докажем, что [math]r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))[/math]. Для каждого множества [math]M[/math] через [math]M^k[/math] обозначим множество всех [math]k[/math]-элементных подмножеств [math]M[/math]. Рассмотрим [math](p+1)[/math]-элементное множество [math]M[/math] и выделим в нём элемент [math]a[/math]. Пусть [math]M_0=M \setminus \{ a \}[/math]. Пусть [math]\rho:M^m\rightarrow \{1, 2 \} [/math] — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\rho': M_0^{m-1} \rightarrow \{1, 2\} [/math] , определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\rho'(B) = \rho(B \cup \{ a \})[/math]. Так как [math]|M_0|=p[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_i \subset M_0[/math], [math]\rho'(B)=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 \{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 \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}[/math] и поэтому [math]\rho(A)=\rho'(A \setminus \{a \})=1[/math]. Учитывая, что [math]|N|=n_1[/math], мы нашли искомое подмножество и в этом случае. При [math]k\gt 2[/math] будем вести индукцию по [math]k[/math] с доказанной выше базой [math]k=2[/math]. При [math]k\gt 2[/math] мы докажем неравенство [math]r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(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 \{0,k\}[/math], в которой цвета [math]1,\ldots,k-1[/math] раскраски [math]\rho[/math] склеены в цвет [math]0[/math]. Тогда существует либо такое подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(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]r_m(n_1,\ldots ,n_k)[/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]H_1,H_2[/math] — графы. Число Рамсея [math]r(H_1,H_2)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что для любого графа [math]G[/math] на [math]x[/math] вершинах либо в [math]G[/math] найдется подграф изоморфный [math]H_1[/math], либо в [math]\overline G[/math] найдется подграф изоморфный [math]H_2[/math].

Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа [math]r(H_1,H_2)[/math] существуют.

Лемма (1):

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

[math]\triangleleft[/math]

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

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

Граф [math]H[/math] называется индуцированным подграфом (англ. induced subgraph) графа [math]G[/math] если две вершины в [math]H[/math] соединены ребром тогда и только тогда, когда они смежны в [math]G[/math].

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

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

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

Индуцированным числом Рамсея (англ. induced Ramsey’s number) [math]r_{ind}(H)[/math] для графа [math]H[/math] будем называть минимальное число [math]x \in \mathbb N[/math], такое что существует рамсеевский граф на [math]x[/math] вершинах для графа [math]H[/math].

Заметим, что при замене произвольного графа [math]H[/math] на клику мы получаем частный случай классической теоремы Рамсея.

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

Для любого графа [math]H[/math] существует рамсеевский граф [math]G[/math].

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

Особенности теории

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

См. также

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

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

• Wikipedia — Ramsey's theorem
• Wikipedia — Ramsey theory
• Ramsey Theory
• An Introduction to Ramsey Theory on Graphs
• Small Ramsey Numbers by Stanisław Radziszowski