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

Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

Числа Рамсея

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

Клика (англ. clique) в неориентированном графе $G = (V, E)$ — подмножество вершин $C \subseteq V$, такое что для любых двух вершин в $C$ существует ребро, их соединяющее.

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

Число Рамсея $r(m, n)$ (англ. Ramsey's number) — наименьшее из таких чисел $x \in \mathbb N$, что при любой раскраске ребер полного графа на $x$ вершинах в два цвета найдется клика на $n$ вершинах с ребрами цвета $1$ или клика на $m$ вершинах с ребрами цвета $2$.

Раскраска $K_5$ без одноцветных треугольников

Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах". Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы $m$ человек были попарно знакомы, или хотя бы $n$ человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея $r(m, n)$, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что $r(3,3) = 6$. Представим, что ребра $K_6$ раскрашены в два цвета: красный и синий. Возьмем вершину $v$. Данной вершине, как и всем другим, инцидентны $5$ рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы $3$ ребра, соединяющие вершину $v$ с вершинами $r$, $s$, $t$, синие. Если хотя бы одно из ребер $rs$, $rt$, $st$ синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, $r(3,3) \le 6$. Чтобы доказать, что $r(3,3) = 6$, предъявим такую раскраску графа $K_5$, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

Теорема Рамсея. Оценки сверху

Теорема (1, Теорема Рамсея):

Для любых $n,m \in \mathbb N$ существует число $r(n,m)$, при этом $r(n,m) \le r(n,m-1)+r(n-1,m)$, а также если числа $r(n,m-1)$ и $r(n-1,m)$ четные, то неравенство принимает вид $r(n,m) \le r(n,m-1)+r(n-1,m) - 1$ .

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

$\triangleright$

$1)$ Докажем с помощью метода математической индукции по $n+m$. База: $r(n,\;1) = r(1,\;n) = 1$, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета. Индукционный переход: Пусть $n\gt 1$ и $m\gt 1$. Рассмотрим полный чёрно-белый граф из $r(n-1,\;m)+r(n,\;m-1)$ вершин. Возьмём произвольную вершину $v$ и обозначим через $M$ и $N$ множества, инцидентные $v$ в чёрном и белом подграфе соответственно. Так как в графе $r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1$ вершин, согласно принципу Дирихле, либо $|M|\geqslant r(n-1,\;m)$, либо $|N|\geqslant r(n,\;m-1)$. Пусть $|M|\geqslant r(n-1,\;m)$. Тогда либо в $M$ существует белый $K_m$, что доказывает теорему, либо в $M$ есть чёрный $K_{n-1}$, который вместе с $v$ образует чёрный $K_n$, в этом случае теорема также доказана. Случай $|N|\geqslant r(n,\;m-1)$ рассматривается аналогично. $2)$ Предположим, $p=r(n-1,\;m)$ и $q=r(n,\;m-1)$ оба чётны. Положим $s=p+q-1$ и рассмотрим чёрно-белый граф из $s$ вершин. Если $d_i$ степень $i$-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, $\sum_{i=1}^s d_i$ — чётно. Поскольку $s$ нечётно, должно существовать чётное $d_i$. Не умаляя общности, положим, что $d_1$ чётно. Обозначим через $M$ и $N$ вершины, ,инцидентные вершине $1$ в чёрном и белом подграфах соответственно. Тогда $|M|=d_1$ и $|N|=s-1-d_1$ оба чётны. Согласно принципу Дирихле, либо $|M|\geqslant p-1$, либо $N\geqslant q$. Так как $|M|$ чётно, а $p-1$ нечётно, первое неравенство можно усилить, так что либо $|M|\geqslant p$, либо $|N|\geqslant q$. Предположим $|M|\geqslant p=r(n-1,\;m)$. Тогда либо подграф, порождённый множеством $M$, содержит белый $K_m$ и доказательство завершено, либо он содержит чёрный $K_{n-1}$, который вместе с вершиной $1$ образует чёрный $K_n$. Случай $|N|\geqslant q=r(n,\;m-1)$ рассматривается аналогично.

$\triangleleft$

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

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

$\triangleright$

Очевидно, $C^{n-1}_{n+m-2}=1$ при $n=1$ или $m=1$, как и соответствующие числа Рамсея. Индукцией по $n$ и $m$ при $n,m \ge 2$ получаем $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}$

$\triangleleft$

Оценки снизу

Теорема (2):

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

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

$\triangleright$

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

$\triangleleft$

Свойства чисел Рамсея

Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея $r(n,m)$ на практике.

• $r(n,m) = r(m,n)$
• $r(1,m) = 1$
• $r(2,m) = m$

Значения чисел Рамсея

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

Числа Рамсея
$n,\ m$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$2$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$3$	$1$	$3$	$6$	$9$	$14$	$18$	$23$	$28$	$36$	$[40, 42]$
$4$	$1$	$4$	$9$	$18$	$25$	$[36, 41]$	$[49, 61]$	$[59, 84]$	$[73, 115]$	$[92, 149]$
$5$	$1$	$5$	$14$	$25$	$[43, 48]$	$[58, 87]$	$[80, 143]$	$[101, 216]$	$[133, 316]$	$[149, 442]$
$6$	$1$	$6$	$18$	$[36, 41]$	$[58, 87]$	$[102, 165]$	$[115, 298]$	$[134, 495]$	$[183, 780]$	$[204, 1171]$
$7$	$1$	$7$	$23$	$[49, 61]$	$[80, 143]$	$[115, 298]$	$[205, 540]$	$[217, 1031]$	$[252, 1713]$	$[292, 2826]$
$8$	$1$	$8$	$28$	$[56, 84]$	$[101, 216]$	$[127, 495]$	$[217, 1031]$	$[282, 1870]$	$[329, 3583]$	$[343, 6090]$
$9$	$1$	$9$	$36$	$[73, 115]$	$[133, 316]$	$[183, 780]$	$[252, 1713]$	$[329, 3583]$	$[565, 6588]$	$[580, 12677]$
$10$	$1$	$10$	$[40, 42]$	$[92, 149]$	$[149, 442]$	$[179, 1171]$	$[289, 2826]$	$[343, 6090]$	$[581, 12677]$	$[798, 23556]$

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

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

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

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

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

Теорема (3):

Пусть $k,n_1,\ldots,n_k \ge 2$ — натуральные числа. Тогда выполняются следующие утверждения: $1) r(k;n_1,\ldots,n_k) \le r(k;n_1-1,n_2,\ldots,n_k)+r(k;n_1,n_2-1,\ldots,n_k)+ \ldots +r(k;n_1,n_2,\ldots,n_k-1)-k+2$ $2)r(k;n_1,\ldots,n_k) \le \dfrac{(n_1+n_2+\ldots+n_k)!}{n_1!\cdot n_2!\cdot \ldots\cdot n_k!}$

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

$\triangleright$

1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 1 2) Доказательство аналогично утверждению 1. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел $n_1,\ldots ,n_k$ равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: $\dfrac{(n_1+n_2+ \ldots +n_k)!}{n_1!\cdot n_2!\cdot \ldots \cdot n_k!}=\sum\limits_{i = 1}^k\dfrac{(n_1+\ldots+(n_i-1)+ \ldots +n_k)!}{n_1!\cdot \ldots \cdot (n_i-1)!\cdot \ldots \cdot n_k!}$ Следовательно, 2 неравенство из данной теоремы выводится из неравенства 1 по индукции.

$\triangleleft$

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

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

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

Нетрудно понять что числа Рамсея размерности $2$ — это определённые ранее числа Рамсея для клик.

При количестве цветов, равном $2$, этот параметр в записи обычно опускают и пишут $r_m(n_1,n_2)$ вместо $r_m(2;n_1,n_2)$.

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

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

Теорема (4):

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

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

$\triangleright$

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

$\triangleleft$

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

Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.

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

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

Из результатов классической теории Рамсея становится понятно, что числа $r(H_1,H_2)$ существуют.

Лемма (1):

Пусть $m\gt 1$, а граф $H$ таков, что $v(H) \ge (m-1)(n-1)+1$ и $\alpha(H) \le m-1$. Тогда граф $H$ содержит в качестве подграфа любое дерево на $n$ вершинах.

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

$\triangleright$

Зафиксируем $m$ и проведем индукцию по $n$. База: для $n=1$ очевидно. Индукционный переход: Пусть верно для $n-1$, докажем для $n$. Рассмотрим произвольное дерево $T_n$ на $n$ вершинах, пусть дерево $T_{n-1}$ получено из $T_n$ удалением висячей вершины. Пусть $U$ — максимальное независимое множестве вершин графа $H$ Тогда $|U|=\alpha(H) \le m-1$, следовательно $v(H-U) \ge (m-1)(n-2)+1$ и очевидно $\alpha(H-U) \le m-1$. По индукционному предположению, граф $H-U$ содержит в качестве подграфа дерево $T_{n-1}$. Пусть $a$ — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево $T_n$. Заметим, что множество $U \cup$ $\{a\}$ не является независимым ввиду максимальности $U$. Следовательно, вершина $a$ смежна хотя с одной вершиной $x \in U$. Отметим, что $x \not\in V(T_{n-1})$ и, присоединив вершину $x$ к вершине $a$ дерева $T_{n-1}$, получим дерево $T_n$ в качестве подграфа графа $H$.

$\triangleleft$

Теорема (5):

$r(T_n,K_m)=(m-1)(n-1)+1$, где $T_n$ — дерево на $n$ вершинах.

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

$\triangleright$

$1)$ Докажем, что $r(T_n,K_m) \ge (m-1)(n-1)+1$. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на $n$ вершинах с рёбрами цвета $1$ и нет клики на $m$ вершинах с рёбрами цвета $2$. Разобьём вершины графа на $m-1$ клику по $n-1$ вершине и покрасим все рёбра этих клик в цвет $1$. Тогда любой связный подграф с рёбрами цвета $1$ содержит не более $n-1$ вершины, в частности, нет подграфа с рёбрами цвета $1$, изоморфного $T_n$. Рёбра цвета $2$ (то есть, все оставшиеся рёбра) образуют $(m-1)$-дольный граф, в котором, очевидно, нет клики на $m$ вершинах. $2)$ Рассмотрим произвольную раскраску рёбер полного графа $K_{(m-1)(n-1)+1}$ в два цвета. Предположим, что не существует клики на $m$ вершинах с рёбрами цвета $2$. Тогда $m\gt 1$ и $\alpha(G_1) \le m-1$. По лемме 1, граф $G_1$ содержит в качестве подграфа любое дерево на $n$ вершинах в частности, дерево, изоморфное $T_n$.

$\triangleleft$

См. также

• Раскраска графа
• Раскраска двудольного графа в два цвета
• Теорема Турана об экстремальном графе

Источники информации

• Wikipedia — Ramsey's theorem
• Wikipedia — Ramsey theory
• An Introduction to Ramsey Theory on Graphs
• Ramsey Theory