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

Текущая версия на 19:21, 4 сентября 2022

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

Содержание

1 Числа Рамсея
2 Числа Рамсея больших размерностей
3 Числа Рамсея для произвольных графов
4 Индуцированная теорема Рамсея
5 Особенности теории
6 См. также
7 Примечания
8 Источники информации

Числа Рамсея

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

Клика (англ. clique) в неориентированном графе — подмножество вершин , такое что для любых двух различных вершин в существует ребро, их соединяющее. Другими словами, клика графа — полный подграф графа .

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

Число Рамсея (англ. Ramsey's number) — наименьшее из таких чисел , что при любой раскраске ребер полного графа на вершинах в два цвета найдется клика на вершинах с ребрами цвета или клика на вершинах с ребрами цвета .

Существует и другое определение для чисел Рамсея.

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

Число Рамсея — это наименьшее из всех таких чисел , что для любого графа на вершинах либо в найдется , либо в найдется граф .

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

Несложно доказать, что данные определения эквивалентны. Достаточно показать, что раскрашенному в два цвета графу [math]K_n[/math], можно однозначно поставить в соответствие граф [math]G[/math] на [math]n[/math] вершинах. Довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"^[1]. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы [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[/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]|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].
Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом, .

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

Для натуральных чисел выполняется равенство

Очевидно, [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] получаем

Оценки снизу

Теорема (2, Теорема Эрдеша):

Для любого натурального числа выполняется неравенство

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

Так как [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](*)[/math]

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

при [math]k \geqslant 3[/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]

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

Теперь обобщим числа Рамсея на произвольное количество цветов.

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

Число Рамсея — это наименьшее из всех таких чисел , что при любой раскраске рёбер полного графа на вершинах в цветов для некоторого обязательно найдётся клика на вершинах с рёбрами цвета .

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

существует число Рамсея , при этом

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

Возьмем граф из вершин и окрасим его рёбра в цветов. Пока что будем считать цвета и одним цветом. Тогда граф будет -цветным. Согласно определению числа Рамсея , такой граф либо содержит для некоторого цвета , такого что , либо , окрашенный общим цветом и . В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный — вершинный граф содержит либо цвета , либо цвета . Таким образом любое число Рамсея для раскраски в цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, существует для любых , и теорема доказана.

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

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

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

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

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

Пусть — натуральные числа, причем , а . Тогда существует число Рамсея .

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

Мы будем доказывать теорему по индукции. Начнем со случая [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]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]B \in M_0^{m-1}[/math] пусть .
Так как [math]|M_0|=p[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_1 \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]|N|=n_1[/math], мы нашли искомое подмножество и в этом случае.
При [math]k\gt 2[/math] будем вести индукцию по [math]k[/math] с доказанной выше базой [math]k=2[/math]. При [math]k\gt 2[/math] мы докажем неравенство .
Для этого мы рассмотрим множество [math]M[/math] на [math]q[/math] вершинах и произвольную раскраску в [math]k[/math]цветов. Рассмотрим раскраску , в которой цвета [math]1,\ldots,k-1[/math] раскраски [math]\rho[/math] склеены в цвет [math]0[/math]. Тогда существует либо такое подмножество [math]M_0 \subset M[/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]r(H_1,H_2)[/math] существуют.

Лемма (1):

Пусть , а граф таков, что и , где — количество вершин в графе . Тогда граф содержит в качестве подграфа любое дерево на вершинах.

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

Зафиксируем [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]\alpha(H-U) \leqslant m-1[/math].

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

Теорема (5, Теорема Хватала):

, где — дерево на вершинах.

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

Сперва докажем, что . Для этого предъявим раскраску рёбер графа [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] вершинах.

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

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

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

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

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

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

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

Индуцированным числом Рамсея (англ. induced Ramsey’s number) для графа будем называть минимальное число , такое что существует рамсеевский граф на вершинах для графа .

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

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

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

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

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

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

См. также

Примечания

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

[1] Theorem on friends and strangers

[2] Induced Ramsey Theorem Proof

[1]

[2]

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

Текущая версия на 19:21, 4 сентября 2022

Содержание

Числа Рамсея

Пример

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

Оценки снизу

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

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

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

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

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

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

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

См. также

Примечания

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты

@@ Строка 1: / Строка 1: @@
-{{В разработке}}
+'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
 ==Числа Рамсея==
-Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на <tex>n</tex> вершинах будем называть кликой.
+{{Определение
-{{Определение|definition=Пусть <tex>m, n \in \mathbb N</tex>. Число Рамсея <tex>r(m, n)</tex> — это наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребром цвета 1 или клика на <tex>m</tex> вершинах с ребром цвета 2.}}
+|id=def1
-===Существование. Оценки сверху===
+|definition='''Клика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex>G(V, E)</tex> {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин]] <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует  [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} [[Основные определения теории графов#defFullGraph|полный]] подграф графа <tex>G(V, E)</tex>. }}
-{{Теорема|id=t1|author=P. Erdos, G. Szekeres
+{{Определение
-|statement=Пусть <tex>n,m \ge 2</tex>-натуральные числа. Тогда <tex>r(n,m) \le r(n,m-1)+r(n-1,m)</tex>. Если оба числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex>-четные, то неравенство строгое.
+|id=def2
+|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}
+Существует и другое определение для чисел Рамсея.
+{{Определение
+|id=def15
+|definition='''Число Рамсея''' <tex>r(n, m)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется <tex>K_n</tex>,  либо в <tex>\overline G</tex> найдется граф <tex>K_m</tex>.
+}}
+[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
+Несложно доказать, что данные определения эквивалентны. Достаточно показать, что раскрашенному  в два цвета графу <tex>K_n</tex>, можно однозначно поставить в соответствие граф <tex>G</tex> на <tex>n</tex> вершинах. Довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы,  или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.
+===Пример===
+Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
+Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа  <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для <tex> K_4</tex>, <tex>K_3</tex> не нужно,  так как достаточно взять  соответствующие подграфы раскрашенного <tex>K_5</tex>.
+===Теорема Рамсея. Оценки сверху===
+{{Теорема|id=ter1|about=1, Теорема Рамсея
+|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
 |proof=
-) Рассмотрим  клику на <tex>r(n, m - 1) + r(n - 1, m)</tex> вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину <tex>a</tex>. Тогда либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n, m - 1)</tex> рёбер цвета 2, либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n—1, m)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на <tex>r(n, m — 1)</tex> вершинах, соединенных с <tex>a</tex> рёбрами цвета 2. На этих вершинах есть либо клика на <tex>n</tex> вершинах с ребрами цвета 1, либо клика на <tex>m—1</tex> вершинах с рёбрами цвета 2. Во втором случае добавим вершину <tex>a</tex> и получим клику на <tex>m</tex> вершинах с рёбрами цвета 2. Теперь из определения <tex>r(n, m)</tex> следует [[#t1|неравенство]].
-) Рассмотрим клику на <tex>r(n, m-l)+r(n-1, m)-1</tex> вершинах с рёбрами цветов 1 и 2 и его произвольную вершину <tex>a</tex>. Если вершине <tex>a</tex> инцидентны хотя бы <tex>r(n,m-1)</tex> рёбер цвета 2 или хотя бы <tex>r(n-1,m)</tex> рёбер цвета 1, то мы найдём в графе клику на <tex>n</tex> вершинах с рёбрами цвета 1 или клику на <tex>m</tex> вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине <tex>a</tex> инцидентны ровно <tex>r(n, m-1)-1</tex> рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего <tex>r(n, m-1)+r(n-1, m)-1</tex> вершин и степень каждой вершины равна <tex>r(n, m-1)-1</tex>. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда <tex>r(n, m-1)</tex> и <tex>r(n-1,m)</tex> — чётные, выполняется неравенство <tex>(n, m)<r(n, m-1)+r(n-1, m)-1</tex>.
+# Докажем с помощью метода математической индукции по <tex>n+m</tex>. <br>'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета. <br>'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества вершин, инцидентных <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex>   вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.
+# Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex> \sum\limits_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>|N|\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>. <br> Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом,  <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex>.
 }}
-{{Утверждение|id=ts1|about=Следствие 1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \le C_{n+m-2}^{n-1}</tex>
+{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
 |proof=
-Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \ge 2</tex> получаем
+Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
-<tex>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}</tex>
+<tex>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}</tex>
 }}
-С помощью неравенства из [[#t1|теоремы]] можно получить несколько точных значений чисел Рамсея.
-Отметим что <tex>r(3,3) \le 2r(2,3)=6</tex>. Так как числа <tex>r(3,3)</tex> и <tex>r(2,4)</tex> четны, можно вывести неравенства <tex>r(3,4) \le r(3,3)+r(2,4)-1=9</tex>. И, наконец, <tex>r(3,5) \le r(2,5)+r(3,4)=14</tex>, а также <tex>r(4,4) \le 2r(3,4)=18</tex>
-===Экстремальные примеры и оценки снизу===
+===Оценки снизу===
-Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.
-{{Определение|id=def2
-|definition=Графом Рамсея <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).
-}}
-Граф <tex>R(3,3)</tex> — это цикл на пяти вершинах. Экстремальный граф <tex>R(3,4)</tex> — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы <tex>R(3,5)</tex> и <tex>R(4,4)</tex> имеют интересную числовую природу.
-Так, если ассоциировать 13 вершин графа <tex>R(3,5)</tex> с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 (то есть, 1, 5, 8 или 12).
+{{Теорема|id=ter2|about=2, Теорема Эрдеша
+|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>
+|proof=
+Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
+Пусть <tex>g(n, k)</tex> доля среди помеченных графов на <tex>n</tex>  вершинах тех, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).
-Если считать 17 вершин графа <tex>R(4,4)</tex> элементами поля вычетов по модулю 17, то рёбра будут соединять вычеты, разность которых — квадратичный вычет по модулю 17 (то есть, 1, 2, 4, 8, 9, 13, 15 или 16).
+Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,
-Существует гипотеза что любой граф <tex>R(k,k)</tex> изоморфен своему дополнению(или что в раскраске полного графа на <tex>r(k,k)-1</tex> вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.
+<tex>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}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>
-{{Теорема|id=t2|author=P. Erdos
+Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем
-|statement=Для любого натурального числа <tex>k \ge 2</tex> выполняется неравенство <tex>r(k,k) \ge k^{k/2}</tex>
-|proof=
-Так как <tex>R(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \ge 3</tex>.
-Зафиксируем множество различных помеченных вершин <tex>v_i,...,v_n</tex>. Пусть <tex>g(n,k)</tex> — деля среди всех графов на вершинах <tex>v_i,...,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных <tex>C^2_n</tex> можно провести или не провести).
-Посчитаем графы с кликой на <tex>k</tex> вершинах так: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образом. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n*2^{C^2_n-C^2_k}</tex>. Следовательно,
+<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>
-<tex>g(n,k) \le \frac{C^k_n}{2^{C^2_k}}<\frac{n^k}{k!*2^{C^2_k}}</tex>
+Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>\langle G, \overline G \rangle</tex>. Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара <tex>\langle G, \overline G \rangle</tex>, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат подграфа на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>2</tex>, получили противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
+}}
-Подставив <tex>n<2^{k/2}</tex> в [[#t2|неравенстве]] мы получаем
-<tex>g(n,k)<\frac{2^{k^2/2}*2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}<\frac12</tex> при <tex>k \ge 3</tex>
+===Свойства чисел Рамсея===
+Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
+* <tex>r(n,m) = r(m,n)</tex>
+* <tex>r(1,m) = 1</tex>
+* <tex>r(2,m) = m</tex>
-Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на n вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\frac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета 1 образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета 1, ни цвета 2, противоречие. Следовательно <tex>r(k,k) \ge 2^{k/2}</tex>.
+===Значения чисел Рамсея===
-}}
+Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют  практически все известные числа Рамсея или же промежутки, в которых они находятся.
-{{Утверждение|id=ts2
+<center>
-|about=Следствие 2
+{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
-|statement=Для любых <tex>k,m \in \mathbb N</tex> таких, что <tex>2 \le k \le m</tex>, выполняется неравенство <tex>r(k,m) \ge 2^{k/2}</tex>
+|+
-}}
+!colspan="11"|Числа Рамсея
+|-align="center"
+! width="6%" |<font color="black"><tex>n,\ m</tex></font>
+! width="6%" |<font color="black"><tex>1 </tex></font>
+! width="6%" |<font color="black"><tex>2 </tex></font>
+! width="6%" |<font color="black"><tex>3 </tex></font>
+! width="6%" |<font color="black"><tex>4 </tex></font>
+! width="6%" |<font color="black"><tex>5 </tex></font>
+! width="6%" |<font color="black"><tex>6 </tex></font>
+! width="6%" |<font color="black"><tex>7 </tex></font>
+! width="6%" |<font color="black"><tex>8 </tex></font>
+! width="6%" |<font color="black"><tex>9 </tex></font>
+! width="6%" |<font color="black"><tex>10</tex></font>
+|-align="center"
+! <font color="black"><tex>1 </tex></font>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+| <tex>1 </tex>
+|-align="center"
+! <font color="black"><tex>2 </tex></font>
+| <tex>1 </tex>
+| <tex>2 </tex>
+| <tex>3 </tex>
+| <tex>4 </tex>
+| <tex>5 </tex>
+| <tex>6 </tex>
+| <tex>7 </tex>
+| <tex>8 </tex>
+| <tex>9 </tex>
+| <tex>10</tex>
+|-align="center"
+! <font color="black"><tex>3</tex></font>
+| <tex>1</tex>
+| <tex>3</tex>
+| <tex>6</tex>
+| <tex>9</tex>
+| <tex>14</tex>
+| <tex>18</tex>
+| <tex>23</tex>
+| <tex>28</tex>
+| <tex>36</tex>
+| <tex>[40, 42]</tex>
+|-align="center"
+! <font color="black"><tex>4</tex></font>
+| <tex>1</tex>
+| <tex>4</tex>
+| <tex>9</tex>
+| <tex>18</tex>
+| <tex>25</tex>
+| <tex>[36, 41]</tex>
+| <tex>[49, 61]</tex>
+| <tex>[59, 84]</tex>
+| <tex>[73, 115]</tex>
+| <tex>[92, 149]</tex>
+|-align="center"
+! <font color="black"><tex>5</tex></font>
+| <tex>1</tex>
+| <tex>5</tex>
+| <tex>14</tex>
+| <tex>25</tex>
+| <tex>[43, 48]</tex>
+| <tex>[58, 87]</tex>
+| <tex>[80, 143]</tex>
+| <tex>[101, 216]</tex>
+| <tex>[133, 316]</tex>
+| <tex>[149, 442]</tex>
+|-align="center"
+! <font color="black"><tex>6</tex></font>
+| <tex>1</tex>
+| <tex>6</tex>
+| <tex>18</tex>
+| <tex>[36, 41]</tex>
+| <tex>[58, 87]</tex>
+| <tex>[102, 165]</tex>
+| <tex>[115, 298]</tex>
+| <tex>[134, 495]</tex>
+| <tex>[183, 780]</tex>
+| <tex>[204, 1171]</tex>
+|-align="center"
+! <font color="black"><tex>7</tex></font>
+| <tex>1</tex>
+| <tex>7</tex>
+| <tex>23</tex>
+| <tex>[49, 61]</tex>
+| <tex>[80, 143]</tex>
+| <tex>[115, 298]</tex>
+| <tex>[205, 540]</tex>
+| <tex>[217, 1031]</tex>
+| <tex>[252, 1713]</tex>
+| <tex>[292, 2826]</tex>
+|-align="center"
+! <font color="black"><tex>8</tex></font>
+| <tex>1</tex>
+| <tex>8</tex>
+| <tex>28</tex>
+| <tex>[56, 84]</tex>
+| <tex>[101, 216]</tex>
+| <tex>[127, 495]</tex>
+| <tex>[217, 1031]</tex>
+| <tex>[282, 1870]</tex>
+| <tex>[329, 3583]</tex>
+| <tex>[343, 6090]</tex>
+|-align="center"
+! <font color="black"><tex>9</tex></font>
+| <tex>1</tex>
+| <tex>9</tex>
+| <tex>36</tex>
+| <tex>[73, 115]</tex>
+| <tex>[133, 316]</tex>
+| <tex>[183, 780]</tex>
+| <tex>[252, 1713]</tex>
+| <tex>[329, 3583]</tex>
+| <tex>[565, 6588]</tex>
+| <tex>[580, 12677]</tex>
+|-align="center"
+! <font color="black"><tex>10</tex></font>
+| <tex>1</tex>
+| <tex>10</tex>
+| <tex>[40, 42]</tex>
+| <tex>[92, 149]</tex>
+| <tex>[149, 442]</tex>
+| <tex>[179, 1171]</tex>
+| <tex>[289, 2826]</tex>
+| <tex>[343, 6090]</tex>
+| <tex>[581, 12677]</tex>
+| <tex>[798, 23556]</tex>
+|}
+</center>
 ===Числа Рамсея для раскрасок в несколько цветов===
+Теперь обобщим числа Рамсея на произвольное количество цветов.
 {{Определение
-|id=def2
+|id=def4
 |definition=
-Пусть <tex>k,n_1,...,n_k \in \mathbb N</tex>. Число Рамсея <tex>r(k;n_1,...,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>.
+'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
 }}
-{{Утверждение
-|id=u3
-|statement=
-Отметим, что <tex>r(2;n,m)</tex> — это определённое ранее число Рамсея <tex>r(n,m)</tex>
-}}
-Обобщение оказывается настолько естественным что по сути не добавляет нам ничего нового:  полностью аналогично [[#t1|теореме]] и [[#ts1|следствию]] можно доказать следующие факты.
 {{Теорема
-|id=t3.
+|id=ter3|about=3,Теорема Рамсея для нескольких цветов
-|statement=Пусть <tex>k,n_1,...,n_k \ge 2</tex> - натуральные числа. Тогда выполняются следующие утверждения:
+|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
-<tex>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</tex>
-<tex>2)r(k;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!*n_2!*...*n_k!}</tex>
 |proof=
-) Доказательстве полностью аналогично пункту 1 доказательства [[#t1|теоремы]]
+Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex>, либо <tex>K_{r(n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
-) Доказательство аналогично [[#ts1|следствию 1]]. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел <tex>n_1,...,n_k</tex> равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению:
-<tex>\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!}</tex>
-Следовательно, 2 неравенство из данной теоремы выводится из неравенства 1 по индукции.
 }}
 ==Числа Рамсея больших размерностей==
 {{Определение
-|id=def5.
+|id=def5
 |definition=
-Пусть <tex>m,k,n_1,...,n_k \in \mathbb N</tex>, причём <tex>n_1,...,n_k \ge m</tex>. Число Рамсея <tex>r_m(k; n_1,...,n_k)</tex> —  наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>.
+Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> —  наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
 }}
-{{Определение
+Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
-|id=def6
-|definition=
-Число <tex>m</tex> называется размерностью числа Рамсея <tex>r_m(k;n_1,...,n_k)</tex>.
-}}
-{{Утверждение
-|id=u2
-|statement=
-) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик
-) При количестве цветов, равном 2, этот параметр мы будем опускать и писать <tex>r_m(n_1,n_2)</tex> вместо <tex>r_m(2;n_1,n_2)</tex>.
-}}
-{{Определение
-|id=def7|definition=
-Для каждою множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
-}}
 {{Теорема
-|id=th5|statement=Пусть <tex>m,k,n_1,...,n_k</tex> - натуральные числа, причем <tex>k \ge 2</tex>, а <tex>n_1,...,n_k \ge m</tex>. Тогда число Рамсея <tex>r_m(k;n_1,...n_k)</tex> существует(то есть, конечно)
+|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
+|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
 |proof=
-)Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что
+# Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>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))</tex>. <br> Для каждого множества <tex>M</tex> через <tex>M^k</tex> обозначим множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>. <br> Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(B) = \rho(B \cup \{ a \})</tex>. <br> Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_1 \subset M_0</tex>,  <tex>\rho'(B)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>,  <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>. <br> По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>,  <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>,  <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.
+# При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство <tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>. <br> Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
-<tex>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))</tex>
-Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M</tex>\{<tex>a</tex>}. Пусть <tex>\alpha:M^m\rightarrow</tex> {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\alpha': M_0^{m-1}\rightarrow</tex> {1,2}, определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\alpha'(В) = \alpha(B U</tex>{a}<tex>)</tex>.
-Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, для которого <tex>\alpha'(В)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, для которого <tex>\alpha'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
-По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex> элементное подмножество <tex>N_1 \subset M_1</tex>, для которого <tex>\alpha(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, для которого <tex>\alpha(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup </tex>{<tex>a</tex>}. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\alpha(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A</tex>\{<tex>a</tex>}<tex>\in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\alpha(A)=\alpha'(A</tex>\{<tex>a</tex>}<tex>)=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.
-)При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство
-<tex>r_m(k;n_1,...,n_k) \le q=r_m(r_m(k-1;n_1,...,n_{k-1}),n_k)</tex>
-Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\alpha:M^m \rightarrow [1..k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\alpha':M^m \rightarrow </tex>{<tex>0,k</tex>}, в которой цвета <tex>1,...,k-1</tex> раскраски <tex>\alpha</tex> склеены в цвет 0. Тогда существует либо таксе подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(k-1;n_1,...,n_{k-1})</tex> и <tex>\alpha'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\alpha(A)=\alpha'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\alpha'(A)=0</tex> следует <tex>\alpha(A) \in [1..k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,...,k-1</tex>
 }}
@@ Строка 123: / Строка 233: @@
 Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
 {{Определение
-|id=def11
+|id=def8
+|definition=
+Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, [[Основные определения теории графов#isomorphic_graphs|изоморфный]] <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
+}}
+Существует и другое определение чисел Рамсея для произвольных графов.
+{{Определение
+|id=def16
 |definition=
-Пусть <tex>H_1,h_2</tex> — два данных графа. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета 1 или подграф изоморфный <tex>H_2</tex> с рёбрами цвета 2
+Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>,  либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex>.
 }}
-В принципе из результатов классической теории Рамсея понятие, что числа <tex>r(H_1,H_2)</tex> обязательно существуют (то есть, конечны).
+Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.
 {{Лемма
-|id=lemma1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
+|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>, где <tex>v(H)</tex> {{---}} количество вершин в графе <tex>H</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево]] на <tex>n</tex> вершинах.
 |proof=
-Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>. База для <tex>n=1</tex> очевидна. Докажем индукционный переход <tex>n-1 \rightarrow n(n>1</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex> Тогда <tex>|U|=\alpha(H) \le m-1</tex>, следовательно <tex>v(H-U) \ge (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \le m-1</tex>.
+Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.
-По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к ксторой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex>{<tex>a</tex>} не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
+'''База:''' для <tex>n=1</tex> очевидно.
+'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множество вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
+По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину, мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x</tex> не принадлежит множеству вершин графа <tex>T_{n-1}</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
 }}
 {{Теорема
-|id=th10
+|id=ter5
-|author=V. Chvatal
+|author=5, Теорема Хватала
-|statement=Пусть <tex>T_n</tex> — дерево на <tex>n</tex> вершинах. Тогда <tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>.
+|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
 |proof=
-) Докажем, что <tex>r(T_n,K_m) \ge (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета 1 и нет клики на <tex>m</tex> вершинах с рёбрами цвета 2. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет 1. Тогда любой связный подграф с рёбрами цвета 1 содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного <tex>T_n</tex>. Рёбра цвета 2 (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
+Сперва докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
+Теперь воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(H_1, H_2)</tex>. Рассмотрим произвольный граф <tex>G</tex> на <tex>{(m-1)(n-1)+1}</tex> вершинах. Предположим, что в графе <tex>G</tex> не существует клики на <tex>m</tex> вершинах. Тогда <tex>m>1</tex> и <tex>\alpha( \overline G) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex> \overline G</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
-) Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета 2. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#lemma1|лемме]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах в частности, дерево, изоморфное <tex>T_n</tex>.
 }}
 ==Индуцированная теорема Рамсея==
-Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.
 {{Определение
-|id=def12
+|id=def9
-|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}
+|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}
-При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>.
-{{Теорема
+{{Определение
-|id=th15.
+|id=def10
-|about=Индуцированная теорема Рамсея
+|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом'''  (англ. ''Ramsey’s graph'') для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}
-|statement=Для любого графа существует рамсеевский граф
-}}
-===Случай двудольного графа===
-Здесь мы будем рассматривать двудольный граф G, как
-G={V1{G),V2{G),E(G))t
+{{Определение
-где Vi(G) и V2{G) — разбиение множества Есршин V[G) на дте дели, а рёбра соединяют вершины из разных долей
+|id=def11
+|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey’s number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex>.}}
+Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.
-Определение 10.7. Пусть H,G — двудольные графы. Инъективное стображение ip : V(H) —> V{G) назовём погружением, если онс удовлетворяет дтум ус л с вням.
-° рШН)) с V1(G), ip(V2(H)) с V2(G) 2° (p(u)tp(v) е E(G) тогда и только тогда когда uv е Е(Н) В этсм случае будем гсЕсрить, что двудольный граф Н погружён в ДЕудольный граф G и использовать обозначение <р(Н) — G(ip(V(H)))
-Замечание 1С.4. Отметим, чте если сушестЕует погружение у> двудольного графа Н в двудольный граф G тс индуцированный подграф р(Н) графа G изоморфен Н
+{{Теорема
-Напомним, чте для множества X через Хк мы обозначаем мнежество Есех fc-элементных подмножеств множества X.
+|id=ter6
-Определение 10.8. Назсьём особым двудольный граф вида
+|about=6, Индуцированная теорема Рамсея
+|statement=Для любого графа <tex>H</tex> существует рамсеевский граф <tex>G</tex>.
+}}
-Я = (V, Vk, Е(Н)),   где   Е(Н) = {xY\x Е V, Y Е Vk, х Е Y}.
+Доказательство <ref>[https://math.la.asu.edu/~andrzej/teach/mat598/lec8.pdf Induced Ramsey Theorem Proof]</ref> данной теоремы было приведено независимо различными математиками, однако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.
-Лемма 10.2. Любой двудольный граф может быть погружен в особый двудольный граф.
-Доказательство. Рассмотрим произвольный двудольный граф Р пусть
-Vl(P) = {°ь • ■ ■ ап}: ЩР) = {h, ■ ■ ■ Ьт}. положим
-V = {ад,. . . , Хп, ?/!,..., уп, Z\, ..., zm}.
-Построим погружение Р в ссобый двудольный граф Н — (V, Vn+1,E)
-Изначально полежим (р(щ) — Xi Попробуем псстрсить такое множество Yj Е Vn+1. чте ip(bj) = Yj. По определению погружения и множества Е{Н). делжве выполняться условие
-У^{хи...,хп} = ч>Ц1р{Ь5)). [ИР]
+==Особенности теории==
-Условие (1С.5) оставляет незаполненными п+1 — dp(bj) > 1 элементов множества Yj (единственное ограничение эти элементы не могут быть вершинами ад,... ,хп). Поместим е Yj элемент-индекс Zj (чтобы Yj ^ Yi ПРН 3 Ф Р, и дополним ироизЕСльнс элементами из yi,...,yn нтсбы в множестве Yj былс рсЕнс п+1 элементов. □
+Результаты, полученные в теории Рамсея, обладают двумя главными характеристиками. Во-первых, они не позволяют получить сами структуры: теоремы лишь доказывают, что они существуют, но алгоритма для их нахождения не предлагают. Единственным способ найти нужную конструкцию зачастую является перебор. Во-вторых, чтобы искомые структуры существовали, обычно требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера конструкции обычно, как минимум, экспоненциальная.
-Лемма 1С.З. Для любого аоуаолъного графа Н сугьестеует такой двудольный граф G, что для любой раскраски рёбер G в два цвета обязательно существует погруженьс ip графа Н в граф G в котором все рёбра р(Н) одноцветны
+==См. также==
-Замечание 10.5. Разумеется, указанный е уел сени леммы 1С.З граф G будет рамсееЕСким графем для Я. Утверждение леммы белее сильное: мы дополнительно требуем, чтобы ьсе вершины одной дели Я можно было погрузить в одну долю графа G.
+*[[Раскраска графа]]
-Доказательство. Венду леммы 1С.2 дестаточне доказать утверждение для оссбогс двудольного графа Я = (V, Vk, Е{Н)). Пусть \V\ — п Докажем чте рамсееЕСким графем для Я будет ссобый двудольный граф G=(U,U2k-\E(G)), где
+*[[Раскраска двудольного графа в два цвета]]
-\U\ = r2k-1{2C%k_1;kn + k- l,...,kn + k- 1). ЦСД
+*[[Теорема Турана об экстремальном графе]]
-Рассмотрим произвольную раскраску рёбер графа G в два иЕета 1 и 2, Каждое множсстес Y Е U2k~1 смежне как Есршнна особого двудольного графа G с 2к — 1 вершиной, хотя бы к из этих рёбер имеет одинаксЕый иЕет Еыберем и зафиксируем для каждого мвсжества Y его подмножество S(Y). состсяшее из к вершин доли U соединённых с Y рёбрами сдинакоЕСго иЕета. Пусть с(У) 6 {1,2} — это пест рёбер соединяющий Y с вершинами из S(Y).
-Можно считать, что элементы U упорядочены Тогда элементы каждого множестЕа Y е и2к~г будут упорядочены. Обозначим через <т(У) мисжество номеров к элементсЕ множества S(Y) в порядке элементов мисжества Y Тогда ег(У) может привимать рсЕвс С^_х значений
-Покрасим множсстес t/2fe_1 (тс есть все (2к — 1)-элементные подмножества [/) в2Скк_1 пестов: цветем подмножества У будет нара (ег(У),с(У)) Из выбора размера мвсжества U (см. условие (1С.6)) следует, что существует такое ЕСдмножестЕС W с U. что |1У| = кп + к — 1 и Есе псд-мвсжества У с \У2к~г имеют одинаковый цвет (сг(У),с(У)) (не умаляя сбшнссти будем считать, что ег(У) = а. с(У) = 1(. Мы найдём погружение графа Н е G(W). все рёбра е котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.
-Занумеруем элементы множестЕа W ь порядке их следования в U пусть W = {гщ,..., Wkn+k-i}- ВЕедем обозначения
-tj = wkj,   T = {tu...,tn},   V — {аь ..., ап}.
-Положим (р((ц) = U. Остаётся корректно определить ip(Z) для каждого мвсжества Z eVk. Прежде чем построить (p(Z) = У 6 и2к~х мы положим S(Y) = {(р(х) : х G Z}. Из определения погружения понятно, что тогда должно выполняться условие S(Y) — У П Т. а следовательно, нам нужно дополнить множество У ешё к — 1 элементами, не входящими в мвсжество Т. Мы сделаем это так, чтобы множестве порядксЕ номеров элементов множества S(Y) среди элементсЕ множества У было <т(У) = о так как U = wki. не входящих е Т элементов W хватит, чтобы обеспечить это.
-Так как по ьыберу мвсжества W мы имеем сг(У) = о. мнежество S(Y) Еыбрано корректно и, опять же е силу ьыбера W. ьсе рёбра особого ДЕудольнсго графа G между Еершинами из S(Y) — {(р(х) : х е Z} и У = ip(Z) покрашены в нвет 1. В завершение остается лишь добавить, что при Z ф Z' мы во построению имеем S(jp(Z)) ф S((p(Z')), поэтому '•p(Z) ф (p(Z'). Таким образом искомое погружение вестроено. □
-===Случай произвольного графа===
+== Примечания==
-Теорема 1С.6. Для щствольного графа Н существует рамсеевский граф,
+<references />
-Доказательство. Пусть к — 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.
+== Источники информации ==
-Выделение одноцветного индуцированного подграфа.
+* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
-Итак, докажем, что G = Gc" и есть рамсеевский граф для Н. Пусть Ри - ■ ■ iPci — именно такая нумерация пар строк в нашей таблице, ь порядке которой совершались шаги перестройки графа. Еассмстрим произвольную раскраску рёбер р графа G ь два цвета и докажем следующий факт.
+* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
-Для каждссс £ е [0..С2] существует изоморфные G1 иьсуьирсван-
+* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
-ный поограф графа G. б котором для пар строк ре+г- .., рс% все рёбра между вершинами ссответстеукших пар строк в раскраске р одноцветны
+*[https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
-Доказательство. Индукция с обратным ходом ст £ — С2п к £ — 0. База для £ = С\ очеЕидна. Докажем переход £ ^ £ — 1
+*[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by  Stanisław Radziszowski]
-Итак рассмотрим наш изоморфный 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. □
+[[Категория:Дискретная математика]]
+[[Категория:Теория графов]]
+[[Категория: Раскраски графов]]