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

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

Числа Рамсея

Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на [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):

Для любого натурального числа [math]k \ge 2[/math] выполняется неравенство [math]r(k,k) \ge k^{k/2}[/math]

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

[math]\triangleright[/math]

Так как [math]R(2,2)=2[/math], достаточно рассмотреть случай [math]k \ge 3[/math]. Зафиксируем множество различных помеченных вершин [math]v_i,...,v_n[/math]. Пусть [math]g(n,k)[/math] — деля среди всех графов на вершинах [math]v_i,...,v_n[/math] тех графов, что содержат клику на [math]k[/math] вершинах. Всего графов на наших вершинах, очевидно [math]2^{C^2_n}[/math] (каждое из возможных [math]C^2_n[/math] можно провести или не провести). Посчитаем графы с кликой на [math]k[/math] вершинах так: существует [math]C^k_n[/math] способов выбрать [math]k[/math] вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образом. Таким образом, каждый граф с кликой на [math]k[/math] вершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем [math]C^k_n*2^{C^2_n-C^2_k}[/math]. Следовательно, [math]g(n,k) \le \frac{C^k_n}{2^{C^2_k}}\lt \frac{n^k}{k!*2^{C^2_k}}[/math] Подставив [math]n\lt 2^{k/2}[/math] в неравенстве мы получаем [math]g(n,k)\lt \frac{2^{k^2/2}*2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}\lt \frac12[/math] при [math]k \ge 3[/math] Предположим, что [math]r(k,k)=n\lt 2^{k/2}[/math] и разобьём все графы на n вершинах на пары [math]G, \overline G[/math] (граф и его дополнение) Так как [math]g(n,k)\lt \frac12[/math], то существует пара, в которой ни [math]G[/math], ни [math]\overline G[/math] не содержат клики на [math]k[/math] вершинах. Рассмотрим раскраску рёбер [math]K_n[/math] в два цвета, в которой ребра цвета 1 образуют граф [math]G[/math]. В такой раскраске нет клики на [math]k[/math] вершинах ни цвета 1, ни цвета 2, противоречие. Следовательно [math]r(k,k) \ge 2^{k/2}[/math].

[math]\triangleleft[/math]

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

Для любых [math]k,m \in \mathbb N[/math] таких, что [math]2 \le k \le m[/math], выполняется неравенство [math]r(k,m) \ge 2^{k/2}[/math]

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

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

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

Утверждение:

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

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

Теорема:

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

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

[math]\triangleright[/math]

1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 2) Доказательство аналогично следствию 1. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел [math]n_1,...,n_k[/math] равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: [math]\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!}[/math] Следовательно, 2 неравенство из данной теоремы выводится из неравенства 1 по индукции.

[math]\triangleleft[/math]

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

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

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