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

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

Числа Рамсея

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

Клика (англ. 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$, так как 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, ни цвета 2, противоречие. Следовательно $r(k,k) \ge 2^{k/2}$.

$\triangleleft$

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

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

Числа Рамсея
$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]$

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

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

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

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

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

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

Теорема (3):

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

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

$\triangleright$

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

$\triangleleft$

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

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

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

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

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

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

1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик 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,...,n_k$ — натуральные числа, причем $k \ge 2$, а $n_1,...,n_k \ge m$. Тогда число Рамсея $r_m(k;n_1,...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,...,n_k) \le q=r_m(r_m(k-1;n_1,...,n_{k-1}),n_k)$ Для этого мы рассмотрим множество $M$ на $q$ вершинах и произвольную раскраску $\rho:M^m \rightarrow [1..k]$ в $k$цветов. Рассмотрим раскраску $\rho':M^m \rightarrow${$0,k$}, в которой цвета $1,...,k-1$ раскраски $\rho$ склеены в цвет 0. Тогда существует либо таксе подмножество $M_0 \subset M$, что $|M_0|=r_m(k-1;n_1,...,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..k-1]$. Исходя из размера множества $M_0$ по индукционному предположению получаем, что найдется искомое подмножество множества $M$ для одного из цветов $1,...,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 \rightarrow n(n\gt 1$. Рассмотрим произвольное дерево $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):

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

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

$\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$

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

Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.

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

Пусть $H$ — граф. Граф $G$ называется рамсеееским графом для $H$, если при любой раскраске рёбер графа $G$ в два цвета существует одноцветный по рёбрам индуцированный подграф графа $G$ изоморфный $H$

При замене произвольного графа $H$ на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа $H$.

Теорема (6, Индуцированная теорема Рамсея):

Для любого графа существует рамсеевский граф

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

Здесь мы будем рассматривать двудольный граф $G$, как

$G=(V_1(G),V_2(G),E(G))$,

где $V_1(G)$ и $V_2(G)$ — разбиение множества вершин $V(G)$ на две доли, а рёбра соединяют вершины из разных долей.

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

Пусть $H,G$ — двудольные графы. Инъективное отображение $\phi:V(H)\rightarrow V(G)$ назовём погружением, если оно удовлетворяет двум условиям. 1)$\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)$ 2)$\phi(u)\phi(v) \in E(G)$ тогда и только тогда когда $uv\in E(H)$ В этом случае будем говорить, что двудольный граф $H$ погружён в двудольный граф $G$ и использовать обозначение $\phi(H)=G(\phi(V(H)))$

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

Отметим, что если существует погружение $\phi$ двудольного графа $H$ в двудольный граф $G$ то индуцированный подграф $\phi(H)$ графа $G$ изоморфен $H$

Напомним, что для множества $X$ через $X^k$ мы обозначаем множество всех $k$-элементных подмножеств множества $X$.

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

Назовем особым двудольный граф вида $H=(V,V^k,E(H))$, где $E(H)=${$xY|x\in V,Y\in V^k, x\in Y$}

Лемма (2):

Любой двудольный граф может быть погружен в особый двудольный граф.

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

$\triangleright$

Рассмотрим произвольный двудольный граф $P$, пусть $V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}$. Положим $V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}$ Построим погружение $P$ в особый двудольный граф $H=(V,V^{n+1},E)$. Изначально положим $\phi(a_i)=x_i$. Попробуем построить такое множество $Y_j\in V^{n+1}$, что $\phi(b_j)=Y_j$. По определению погружения и множества $E(H)$, должно выполняться условие: $Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)$ Условие оставляет незаполненными $n+1-d_P(b_j)\ge 1$ элементов множества $Y_j$ (единственное ограничение эти элементы не могут быть вершинами $x_1,...,x_n$). Поместим в $Y_j$ элемент-индекс $z_j$ (чтобы $Y_j\not=Y_l$ при $j \not=l$, и дополним произвольно элементами из $y_1,...,y_n$, чтобы в множестве $Y_j$ было ровно $n+1$ элементов.

$\triangleleft$

Лемма (3):

Для любого двудольного графа $H$ существует такой двудольный граф $G$, что для любой раскраски рёбер $G$ в два цвета обязательно существует погружение $\phi$ графа $H$ в граф $G$ в котором все рёбра $\phi(H)$ одноцветны.

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

$\triangleright$

Утверждение (6): Разумеется, указанный в условии леммы 3 граф $G$ будет рамсеевским графом для $H$. Утверждение леммы более сильное: мы дополнительно требуем, чтобы все вершины одной доли $H$ можно было погрузить в одну долю графа $G$. Ввиду леммы 2 достаточно доказать утверждение для особого двудольного графа $H=(V,V^k,E(H))$. Пусть $|V|=n$. Докажем что рамсеевским графом для $H$ будет особый двудольный граф $G=(U,U^{2k-1},E(G))$, где $|U|=r_{2k-1}(2C^k_{2k-1};kn+k-1,...,kn+k-1).$ ** Рассмотрим произвольную раскраску рёбер графа $G$ в два цвета 1 и 2. Каждое множество $Y\in U^{2k-1}$ смежно как вершина особого двудольного графа $G$ с $2k-1$ вершиной, хотя бы $k$ из этих рёбер имеет одинаковый цвет. Выберем и зафиксируем для каждого множества $Y$ его подмножество $S(Y)$, состоящее из $k$ вершин доли $U$ соединённых с $Y$ рёбрами одинакового цвета. Пусть $c(Y)\in \{1,2\}$ — это цвет рёбер соединяющий $Y$ с вершинами из $S(Y)$. Можно считать, что элементы $U$ упорядочены. Тогда элементы каждого множества $Y\in U^{2k-1}$ будут упорядочены. Обозначим через $\sigma(Y)$ множество номеров $k$ элементов множества $S(Y)$ в порядке элементов множества $Y$. Тогда $\sigma(Y)$ может принимать ровно $C^k_{2k-1}$ значений. Покрасим множество $U^{2k-1}$ (то есть все $(2k-1)$-элементные подмножества $U$) в $2C^k_{2k-1}$цветов: цветом подмножества $Y$ будет пара $(\sigma(Y),c(Y))$. Из выбора размера множества $U$ (см. условие **) следует, что ceotcndetn такое подмножество $W\subset U$, что $|W|=kn+k-1$ и все подмножества $Y\subset W^{2k-1}$ имеют одинаковый цвет $(\sigma(Y),c(Y))$ (не умаляя общности будем считать, что $\sigma(Y)=\sigma, c(Y)=1)$. Мы найдём погружение графа $H$ в $G(W)$, все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму. Занумеруем элементы множества $W$ в порядке их следования в $U$: пусть $W=\{w_1,...,w_{kn+k-1}\}$. Введем обозначения $t_j=w_kj, T=\{t_1,...,t_n\}, V=\{a_1,...,a_n\}$. Положим $\phi(a_i)=t_i$. Остаётся корректно определить $\phi(Z)$ для каждого множества $Z\in V^k$. Прежде чем построить $\phi(Z)=Y\in U^{2k-1}$ мы положим $S(Y)=\{\phi(x):x\in Z\}$. Из определения погружения понятно, что тогда должно выполняться условие $S(Y)=Y\cap T$, а следовательно, нам нужно дополнить множество $Y$ еще $k-1$ элементами, не входящими в множество $T$. Мы сделаем это так, чтобы множество порядков номеров элементов множества $S(Y)$ среди элементов множества $Y$ было $\sigma(Y)=\sigma$: так как $t_i=w_ki$, не входящих в $T$ элементов $W$ хватит, чтобы обеспечить это. Так как по выбору множества $W$ мы имеем $\sigma(Y)=\sigma$, множество $S(Y)$ выбрано корректно и, опять же в силу выбора $W$, все рёбра особого двудольного графа $G$ между вершинами из $S(Y)=\{\phi(x):x\in Z\}$ и $Y=\phi(Z)$ покрашены в цвет 1. В завершение остается лишь добавить, что при $Z\not=Z'$ мы по построению имеем $S(\phi(Z))\not=S(\phi(Z'))$, поэтому $\phi(Z)\not=\phi(Z')$. Таким образом искомое погружение построено.

$\triangleleft$

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

Теорема (7):

Для произвольного графа $H$ существует рамсеевский граф.

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

$\triangleright$

Пусть $k=v(H),n=r(k,k)$. Пронумеруем вершины графа $H$. Построим граф $G^0$ следующим образом: разместим его вершины в виде таблице $n \times C^k_n$. Таким образом в каждом столбце вершины окажутся пронумерованы числами от 1 до $n$, как соответствующие строки таблицы. В каждом столбце одним из $C^k_n$ способов разместим граф $H$ (каждый столбец соответствует одному из возможных способов размещения). Все рёбра графа $G^0$ будут рёбрами указанных копий графа $H$. Граф $G^0$ является $n$-дольным, его естественное разбиение на доли задаётся таблицей: $V_i(G^0)$ — это вершины, соответствующие $i$ ряду таблицы. Мы последовательно в несколько шагов будем перестраивать наш граф с помощью леммы 3, так, чтобы вершины последующих графов также разбивались на $n$ долей и записывались в виде таблицы. Каждый шаг будет соответствовать одной паре строк таблицы. Шаг перестройки графа. Итак, пусть мы имеем $n$-дольный граф $G^l$, доли которого $V_i=V_i(G^l)$ (где $i\in [1..n]$). Пусть с парой строк (и, соответственно, долей) $i,j$ мы еще не выполняли шаг. Очевидно, граф $G_{i,j}=G^l(V_i\cup V_j)$ двудолен и для него по лемме 3 существует двудольный рамсеевский граф $P_{i,j}$. Более того если вершины $P_{i,j}$ разбиты на две доли $W_i$ и $W_j$, то для любой раскраски рёбер в два цвета существует одноцветное погружение $\phi$ графа $G_{i,j}$ в $P_{i,j}$ в котором $\phi(V_i)\subset W_i$ и $\phi(V_j)\subset W_j$. Назовём таксе погружение одноцветным. Перейдём к построению $G^{l+1}$. Заменим $V_i$ на $W_i$ и $V_j$ на $W_j$, проведем между этими долями все рёбра графа $P_{i,j}$. Наша цель в том, чтобы для любого погружения $G_{i,j}$ в $P_{i,j}$ была содержащая его копия $G^l$ (причем доли этой копии лежали в соответствующих строках таблицы графа $G^{l+1}$ Занумеруем всевозможные погружения $G_{i,j}$ в $P_{i,j}$: пусть это $G_{i,j}(1),...,G_{i,j}(q)$. Каждому погружению $G_{i,j}(s)$ мы поставим в соответствие отдельные копии всех отличных от $V_i$ и $V_j$ долей: $V_1(s),...,V_n(s)$. Положим $V_i(s)=V(G_{i,j}(s))\cap W_i$ и $V_j(s)=V(G_{i,j}(s))\cap W_j$. На этих долях построим копию графа $G^l$. В результате для каждого погружения графа $G_{i,j}$ в $P_{i,j}$ мы построили свою копию графа $G^l$. Выделение одноцветного индуцированного подграфа. Итак, докажем, что $G=G^{C^2_n}$ и есть рамсеевский граф для $H$. Пусть $p_1,...,p_{C^2_n}$ — именно такая нумерация пар строк в нашей таблице, в порядке которой совершались шаги перестройки графа. Рассмотрим произвольную раскраску рёбер $\rho$ графа $G$ в два цвета и докажем следующий факт. Утверждение (7): Для каждого $l\in [0..C^2_n]$ существует изоморфный $G^l$ индуцированный подграф графа $G$, в котором для пар строк $p_{l+1},...,p_{C^2_n}$ все рёбра между вершинами соответствующих пар строк в раскраске $\rho$ одноцветны. $\triangleright$ Индукция с обратным ходом от $l=C^2_n$ к $l=0$. База для $l=C^2_n$ очевидна. Докажем переход $l\rightarrow l-1$ Итак рассмотрим наш изоморфный $G^l$ подграф, который мы для простоты будем обозначать $G^l$ и пару строку $p_l$ в нем: пусть это строки $i$ и $j$, a $P_{i,j}$ и $G_{i,j}$ — те двудольные графы между этими строками, что описаны в шаге построения. Так как $P_{i,j}$ (подграф графа $G^l$) — рамсеевский граф для $G_{i,j}$, мы можем выбрать одноцветное в раскраске $\rho$ погружение $G_{i,j}$ в $P_{i,j}$ и соответствующая ему по построению копия $G^{l-1}$ будет искомым (из построения очевидно, что индуцированным!) подграфом $G^l$ а значит, и $G$ $\triangleleft$ Таким образом, существует изоморфный $G^0$ индуцированный под­граф графа $G$, в котором для каждой пары строк $i,j$ все ребра между вершинами соответствующих строк одноцветны в раскраске $\rho$. Будем обозначать этот граф просто $G^0$. Рассмотрим граф $K_n$, вершины которого соответствуют строкам таблицы и покрасим каждое ребро в цвет, в который покрашены рёбра $G^0$ между соответствующими строками. Так как $n=r(k,k)$, существуют $k$ вершин, между которыми все рёбра одноцветны. Рассмотрим столбец графа $G^0$, в котором $H$ размещён именно в строчках, соответствующих этим $k$ вершинам. Подграф $H'$ графа $G^0$ на вершинах этого столбца и соответствующих строчках изоморфен $H$, по построению является индуцированным подграфом графа $G^0$ и все его рёбра одноцветны в раскраске $\rho$. Остаётся лишь заметить, что $H'$ — индуцированный подграф графа $G$.

$\triangleleft$

См. также

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

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

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