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

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

Числа Рамсея

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

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

Определение 10.3. Пусть то, к, ni,..., пк £ N причём щ,..., пк > то, Число Рамсея rm(k; rii,..., пк) — зто наименьшее из Есех таких чисел х £ N, чте при л к бой раскраске то-элементных подмножеств ж-элементнего множестьа М в к пестов для нскстсрсго г £ [1..к] обязательно найдётся таксе множестьо чте |ИД — щ в ьсе m-злементные подмножестьа множестьа Wi имеют нвет г. Число то называется размерностью числа Рамсея rm(fc;ni,... ,пк). Замечание 10.3, 1) Нетрудно пенять что числа Рамсея размеры сети 2 — эте определённые выше числа Рамсея для клик 2) При количестве цветов, равном 2, зтот параметр мы будем спускать и писать rm(ni,n2) вместе rm(2;ni,n2). Определение 1С.4. Для каждою множества М через Мк мы будем обозначать множество всех fc-элементных подмножеств М. Теорема 10,4. Пусть то, fc,ni,... ,пк — патуралънье число, причём к > 2. ani,... ,пк > т. Тогда число Рамсея rm(k;ni,... ,пк) существует) (то eemt ксиечьоу Доказательство, 1, Мы будем доказывать теорему пс индукции. Нач­нем сс случая к = 2. Приступая к доказательству для числа rm(ni,n2) мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности то с меньшей суммей ni+n2. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что

Гт{пЪ П2) - 1 < р = rm_i(rm(?Ti - 1, П2), Гт(пЬ П2 - 1)).

Рассмотрим (р+1)-элементное множество М и выделим в нём элемент а. Пусть М0 — М\ {а}. Пусть р : Мт —> {1,2} — произвольная раскраска в деэ нЕСта. Рассмотрим раскраску р' : М™-1 —> {1,2}. определённую следующим сбразом: для каждого мнежества В £ М™-1 пусть р'(В) = p(BU{a}). Так как \М0\ = р либо существует rm(ni — 1, ?г2)-злементное под­множестве Mi с М0, для кет ер его р'(В) — 1 на всех В £ Mf1-1. либо существует rm(ni,n2 — 1)-элементнсе подмнсжество М2 С М0. для ко-тсрсю р'(В) = 2 на всех В е М™'1. Случаи аналсгичны, рассмотрим первый случай и множество Мх Пс индукнионнсму предположен и к не |Mi| = rm{n\ — 1,п2) следует что либс существует п\ — 1 элементнсе подмнсжество Nx С Mi- для кото-рсго р(А) = 1 на всех А £ N™, либо существует п2-эле мен тис с подмноже­ство N2 С Mi, для которого р{А) = 2 на Есех А £ N™. Вс втором случае искомое подмножество найдено (это N2). рассмотрим перЕый случай и множество N = N± U{a}. Пуств А £ Nm. Если А $ а то А £ iVf1 и следо­вательно р(А) = I. Если же А э а. тс множестве А\{а} £ N™'1 с М™-1 и петому = \ {а}) = 1. Учитывая, что \N\ = ni, мы нашли искомое подмножество и в этом случае 2. При к > 2 будем Еести индукцию по к с доказанной выше базей к = 2. При к > 2 мы докажем неравенстве

rm(k;nx, ...,nk) [l..k] е /с цестов. Рассмотрим раскраску р' : Мт -д {О, А;}, е которой цвета 1,..., fc — 1 раскраски р склеены в цвет С. Тогда существует либс таксе подмножество М0 С М что |М0| = гт(/ь — 1; ni,..., ?Tfc_i) и р'(Д) = 0 на всех А £ М™. либо сушестЕует такое г^-злементное педмножестпе с М. что р(А) = р'{А) — к на Есех А 6 М£\ Во Егерем случае Мк — искомое подмножество а е пер-есм случае заметим чте на любом подмножестве А £ М™ из р'{А) = О следует р{А) £ [l..fc — 1]. Исходя из размера множества М0 по индукни-еннсму предположению получаем, чте найдется искомое подмнсжество множества М для одного из цветов 1,..., к — 1 □

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

Еще один способ обобщения классической теории Рамсея — замена клик на произЕСлвные графы-шаблоны, Определение 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 содержит е качестве подграфа любее дерево на п вершинах в частности, дереве, иземерфнее Тп. □

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

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

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