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

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

Числа Рамсея

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

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

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

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

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

Пусть [math]n,m \ge 2[/math]-натуральные числа. Тогда [math]r(n,m) \le r(n,m-1)+r(n-1,m)[/math]. Если оба числа [math]r(n,m-1)[/math] и [math]r(n-1,m)[/math]-четные, то неравенство строгое.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Для натуральных чисел [math]m,n[/math] выполняется равенство [math]r(n,m) \le C_{n+m-2}^{n-1}[/math]

[math]\triangleright[/math]

Очевидно, [math]C^{n-1}_{n+m-2}=1[/math] при [math]n=1[/math] или [math]m=1[/math], как и соответствующие числа Рамсея. Индукцией по [math]n[/math] и [math]m[/math] при [math]n,m \ge 2[/math] получаем [math]r(n,m) \le r(n,m-1)+r(n-1,m) \le C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}[/math]

[math]\triangleleft[/math]

С помощью неравенства из теоремы можно получить несколько точных значений чисел Рамсея. Отметим что [math]r(3,3) \le 2r(2,3)=6[/math]. Так как числа [math]r(3,3)[/math] и [math]r(2,4)[/math] четны, можно вывести неравенства [math]r(3,4) \le r(3,3)+r(2,4)-1=9[/math]. И, наконец, [math]r(3,5) \le r(2,5)+r(3,4)=14[/math], а также [math]r(4,4) \le 2r(3,4)=18[/math]

Экстремальные примеры и оценки снизу

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

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

Графом Рамсея [math]R(n,m)[/math] назовем такой граф на [math]r(n,m)-1[/math] вершинах, не содержащий ни клики на [math]n[/math] вершинах ни независимого множества на [math]m[/math] вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа [math]K_{r(m,n)-1}[/math], не содержащей ни клики на [math]n[/math] вершинах с рёбрами цвета 1 ни клики на [math]m[/math] вершинах с рёбрами цвета 2).

Граф /2(3,3) — зто никл на пяти вершинах Экстремальный граф /2(3,4) — это никл на 8 ьершинах с проведёнными четырьмя главны­ми диагоналями Графы /2(3,5) и /2(4,4) имеют интересную числовую природу, Так, если асссниирсвать 13 Еершнн графа /2(3,5) с элементами по­ля вычетоЕ по модулю 13 тс рёбра будут соединять вычеты разнссть которых — кубический Еычет не модулю 13 (то есть, 1. 5, 8 или 11] Если считать 17 Еершнн графа /2(4,4) элементами поля ЕычетсЕ по модулю 17. то рёбра будут соединять Еычеты, разнссть которых — квад­ратичный ьычет пс модулю 17 (то есть, 1.2,48,9.13,15 или 11). Существует гипотеза что любой граф R(k,k) изоморфен своему до­полнению (или что е раскраске полного графа на г(к,к) — 1 вершинах в два цвета граф с рёбрами тега 1 обязательно изсмсрфен графу с рёбрами цЕета 1]. Однако, зто не белее чем краснЕсе предположение, е обоснование которого межно положите лишь нем неги е известные при­меры. Теорема 10.2. (P. Eidos. 1947.) Для любого натурального числа к>2 выполняется неравенство г(к,к) > 2к/2 Доказательство. Так как г(2,2) = 2, достаточно рассмотреть случай к > 3. зафиксируем множестес различных помеченных вершин vi,...,vn. Пусть д(п,к) — деля среди всех графсЕ на Еершинах vi,...,vn тех гра­фов, что содержат клику на к вершинах Есегс графсЕ на наших Еер­шинах счеЕндно 2С« (каждое из возможных С2 можно провести или не провести). Посчитаем графы с кликой на к Еершинах так: сушествует Ск спо­собов Еыбрать к вершин для клики в нашем множестве, после чегс все рёбра между ними будем считать проведенными, а остальные ребра вы­бираются произвольным сбразом. Таким сбразом, каждый граф с кли­кой на к Еершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой сказывается не более, чем С£-2с"_сю Следовательнс, Ск пк д(п,к) < -£ < —(1С.2s 2С1 к\ -2С1 ПсдстаЕИЕ п < 2fe/2 е неравенстве (1С.2) мы получаем 2fc2/2 . 2-с| 2fc/2 i д(п, к) < = — < - при к > 3.

Предположим, что r(k,k) = п < 2к12 и разобьём Есе графы на п вершинах на пары G, G (граф и егс дополнение) Так как д(п,к) < \. то существует пара, е которой ни G. ни G не содержат клики на к Еершинах. Рассмотрим раскраску рёбер Кп е два цвета, в которой ребра цвета 1 образуют граф G. В такой раскраске нет клики на к вершинах ни цвета 1, ни нвета 2, прстиЕоречне Следовательнс, г(к,к) > 2к12. □ Следствие 1С.2. Для, любых к,т G N таких, что 2 < к < т. выпол­няется неравенстве г(к,т) > 2к12 Удивительно, не изЕсетные конструкции не могут ни дать более точ­ную оценку на г(к,к). чем в теореме 10 2, ни дать более точную опенку на г(к,т), чем в следствии 10 2,

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

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

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

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