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

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

Числа Рамсея

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

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

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

Граф [math]R(3,3)[/math] — это цикл на пяти вершинах. Экстремальный граф [math]R(3,4)[/math] — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы [math]R(3,5)[/math] и [math]R(4,4)[/math] имеют интересную числовую природу.

Так, если ассоциировать 13 вершин графа [math]R(3,5)[/math] с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 (то есть, 1, 5, 8 или 12).

Если считать 17 вершин графа [math]R(4,4)[/math] элементами поля вычетов по модулю 17, то рёбра будут соединять вычеты, разность которых — квадратичный вычет по модулю 17 (то есть, 1, 2, 4, 8, 9, 13, 15 или 16).

Существует гипотеза что любой граф [math]R(k,k)[/math] изоморфен своему дополнению(или что в раскраске полного графа на [math]r(k,k)-1[/math] вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.

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

Для любого натурального числа k>=2 выполняется неравенство r(k,k)>=k^k/2

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

[math]\triangleright[/math]

Так как г(2,2) = 2, достаточно рассмотреть случай к > 3. зафиксируем множестес различных помеченных вершин vi,...,vn. Пусть д(п,к) — деля среди всех графсЕ на Еершинах vi,...,vn тех гра­фов, что содержат клику на к вершинах Есегс графсЕ на наших Еер­шинах счеЕндно 2С« (каждое из возможных С2 можно провести или не провести). Посчитаем графы с кликой на к Еершинах так: сушествует Ск спо­собов Еыбрать к вершин для клики в нашем множестве, после чегс все рёбра между ними будем считать проведенными, а остальные ребра вы­бираются произвольным сбразом. Таким сбразом, каждый граф с кли­кой на к Еершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой сказывается не более, чем С£-2с"_сю Следовательнс, Ск пк д(п,к) < -£ < —(1С.2s 2С1 к\ -2С1 ПсдстаЕИЕ п < 2fe/2 е неравенстве (1С.2) мы получаем 2fc2/2 . 2-с

[math]\triangleleft[/math]

Следствие 1С.2. Для, любых к,т G N таких, что 2 < к < т. выпол­няется неравенстве г(к,т) > 2к12 Удивительно, не изЕсетные конструкции не могут ни дать более точ­ную оценку на г(к,к). чем в теореме 10 2, ни дать более точную опенку на г(к,т), чем в следствии 10 2,

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

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

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

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