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

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

Числа Рамсея

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

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

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

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

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

Число [math]m[/math] называется размерностью числа Рамсея [math]r_m(k;n_1,...,n_k)[/math].

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

1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик 2) При количестве цветов, равном 2, этот параметр мы будем опускать и писать [math]r_m(n_1,n_2)[/math] вместо [math]r_m(2;n_1,n_2)[/math].

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

Для каждою множества [math]M[/math] через [math]M^k[/math] мы будем обозначать множество всех [math]k[/math]-элементных подмножеств [math]M[/math].

Теорема:

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

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

[math]\triangleright[/math]

Мы будем доказывать теорему по индукции. Начнем со случая [math]k=2[/math]. Приступая к доказательству для числа [math]r_m(n_1,n_2)[/math] мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности [math]m[/math] с меньшей суммой [math]n_1+n_2[/math]. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что [math]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))[/math] Рассмотрим [math](p+1)[/math]-элементное множество [math]M[/math] и выделим в нём элемент [math]a[/math]. Пусть [math]M_0=M[/math]\{[math]a[/math]}. Пусть [math]\alpha:M^m\rightarrow[/math] {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\alpha': M_0^{m-1}\rightarrow[/math] {1,2}, определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\alpha'(В) = \alpha(B U[/math]{a}[math])[/math]. Так как [math]|M_0|=р[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_i \subset M_0[/math], для которого [math]\alpha'(В)=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]\alpha'(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]\alpha(A)=1[/math] на всех [math]A \in N^m_1[/math], либо существует [math]n_2[/math]-элементное подмножество [math]N_2 \subset M_1[/math], для которого [math]\alpha(A)=2[/math] на всех [math]A \in N_2^m[/math]. Во втором случае искомое подмножество найдено (это [math]N_2[/math]), рассмотрим первый случай и множество [math]N=N_1 \cup [/math]{[math]a[/math]}. Пусть [math]A \in N^m[/math]. Если [math]A \not\ni a[/math], то [math]A \in N_1^m[/math] и следовательно [math]\alpha(A)=1[/math]. Если же [math]A \ni a[/math], то множество [math]A[/math]\{[math]а[/math]}[math]\in N_1^{m-1} \subset M_1^{m-1}[/math] и поэтому [math]\alpha(A)=\alpha'(A[/math]\{[math]a[/math]}[math])=1[/math]. Учитывая, что [math]|N|=n_1[/math], мы нашли искомое подмножество и в этом случае

[math]\triangleleft[/math]

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

Еще один способ обобщения классической теории Рамсея — замена клик на произЕСлвные графы-шаблоны, Определение 1С.5. Пусть Нх,Н2 — два данных графа. Висло Рамсея г(Нх,Н2) — зто наименьшее из всех таких чисел ж £ N что при любой раскраске рёбер полного врафа на х вершинах е два цвета обязатель­но найдется подграф, изоморфный Нх с рёбрами цвета ] или педграф изоморфный Н2 с рёбрами цвета 2 Е принципе из результатов классической теории Рамсея понятие, чте числа г(Нх, Н2) обязательно существуют (тс есть, конечны". Интересно, что иногда их можно точно вычислить,

Лемма 10.1, Пусть т > 1, а граф Н такое. чтои(Н) > (то—1)(п—1)+1 и <у.{Н) < то — 1. Тосоа граф Н содержит е качестве посграфа лкбсе дереве ьап вершинах

Доказательство, Зафиксируем т и проведем индукцию не п. База для п — 1 очевидна. Докажем индукционный переход п — 1 —> п (п > 1), Рассмотрим произвольнее дереис Тп на п иершинах. пусть дереЕС Tn_i получено из Тп удалением висячей Еергнины Пусть U — максимальнее независимое множестве ьершин графа Н Тогда \U\ = а(РР) < m — 1. следовательно v{H—U) > (то—1)(п-2)+1 и очевидно a(H-U) < m—1. По индукционному предположению, граф H — U содержит в качестве подграфа дерево Tn_i Пусть а — Еерглина этого дерева, присоединив к ксторей Еисячую ьершину мы получим дереве Тп. Заметим, чте множе­ство U U {а} не является независимым ввиду максимальности U. следо­вательно, вершина а смежна хотя с одней Есршнной х Е U. Стметим, что х 0 V(Tn-i) и, присоединив ьершину х к ьершине а дерева Tn_i, получим дереЕС Тп е качестве подграфа графа Н. □

Теорема 10.5. (V. Chvatal) Пусть Тп — дерево на п верьиьпах. Тогоа r(Tn,Km) = (m-l)(n-l) + l.

Доказательство, 1] Докажем, что r(Tn, Кт) > (т — 1)(п — 1) + 1. Для этего нредъяЕим раскраску рёбер графа ^(т.-1)(тг-1) е ксторей нет ни одного СЕязногс подграфа на п Еершинах с рёбрами цвета 1 и нет клики на т вершинах с рёбрами цвета 2. Разсбьём Есршнны графа ш т—1 клику по п— 1 вершине и покрасим Есе рёбра этих клик в цвет 1, Тогда любой сеязный подграф с рёбрами цвета 1 содержит не белее п— 1 вер­шины, в частности, нет подграфа с рёбрами цвета 1, изоморфного Тп. Рёбра цвета 2 (тс есть, Есе оставшиеся рёбра) образуют (то — 1)-дсльный граф е котором, счевидне, нет клики на то вершинах 1) Рассмотрим нроизЕСльную раскраску рёбер полного графа K(m-i)(n-i)+i в два цвета. Предположим, что не сушестьует клнки на то вершинах с рёбрами цвета 2. Тсгда то > 1 и a(Gi) < m—1. По лемме 10 1, граф Gi содержит е качестве подграфа любее дерево на п вершинах в частности, дереве, иземерфнее Тп. □