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

Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.

Формулировки

Теоретико-множественная формулировка

Частный случай N(p, q, r)

Пусть $p$, $q$ и $r$ — натуральные числа, причём $p,q⩾r$.

Тогда существует число $N=N(p,q,r)$, обладающее следующим свойством: если все $r$-элементные подмножества $N$-элементного множества $S$ произвольным образом разбиты на два непересекающихся семейства $\alpha$ и $\beta$, то либо существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся в $\alpha$, либо существует $q$-элементное подмножество, все $r$-элементные подмножества которого содержатся в $\beta$.

Общий случай

Пусть множество $S$ имеет $N$ элементов. Рассмотрим его $r$-подмножества $r⩾1$, обозначим совокупность всех этих подмножеств $P_r(S)$, упорядоченные $t$-разбиения $P_r(S)=A_1\cup A_2\cup \dots \cup A_t$, числа $q_1,q_2,\dots ,q_t$, задающие разбиение $1⩽r⩽q_1,q_2,\dots ,q_t$.

Тогда для любого упорядоченного $t$-разбиения множества $P_r(S)$ существует такое минимальное число $N(q_1,q_2,\dots ,q_t;r)$, что если $N⩾N(q_1,q_2,\dots ,q_t;r)$, то существует $(q_i,A_i)$ — подмножество множества $S$, то есть такое $q_i$-подмножество множества $S$, все $r$-подмножества которого содержатся в $A_i,1⩽t⩽t$Шаблон:Sfn.

Формулировка на языке теории графов

Для любых $c$ натуральных чисел $n_1,n_2,\dots ,n_c$ в любой $c$-цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с $n_i$ вершинами для некоторого цвета $i$. В частности, для любых $r$ и $s$, достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из $r$ вершин, либо полный белый подграф из $s$ вершин.

Числа Рамсея

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

Минимальное число $R(r,s)$, при котором этоШаблон:Что? выполнено, называют числом Рамсея.

Например, равенство $R(3,3)=6$ означает, что с одной стороны в любой двухцветной раскраске полного графа $K_6$ найдётся одноцветный треугольник, а с другой стороны — то, что полный граф $K_5$ допускает двухцветную раскраску без одноцветных треугольников.

В общем случае для $c$-цветной раскраски используется обозначение $R(n_1,n_2,\dots ,n_c)$ для минимального числа вершин, обеспечивающего существование $K_{n_i}$ для некоторого цвета $i$.

Доказательство теоремы Рамсея

Двухцветный случай

Лемма 1. $R(r,s)⩽R(r-1,s)+R(r,s-1).$

Доказательство. Докажем с помощью метода математической индукции по $r+s$.

База индукции. $R(n,1)=R(1,n)=1$, так как 1-вершинный граф можно считать полным графом любого цвета.

Индукционный переход. Пусть $r>1$ и $s>1$. Рассмотрим полный чёрно-белый граф из $R(r-1,s)+R(r,s-1)$ вершин. Возьмём произвольную вершину $v$ и обозначим через $M$ и $N$ множества инцидентные $v$ в чёрном и белом подграфе соответственно. Так как в графе $R(r-1,s)+R(r,s-1)=|M|+|N|+1$ вершин, согласно принципу Дирихле (комбинаторика), либо $|M|⩾R(r-1,s)$, либо $|N|⩾R(r,s-1)$.

Пусть $|M|⩾R(r-1,s)$. Тогда либо в $M$ (и следовательно во всём графе) есть белый $K_s$, что завершает доказательство, либо в $M$ есть чёрный $K_{r-1}$, который вместе с $v$ образует чёрный $K_r$. Случай $|N|⩾R(r,s-1)$ рассматривается аналогично.

Замечание. Если $R(r-1,s)$ и $R(r,s-1)$ оба чётны, неравенство можно усилить: $R(r,s)⩽R(r-1,s)+R(r,s-1)-1$.

Доказательство. Предположим, $p=R(r-1,s)$ и $q=R(r,s-1)$ оба чётны. Положим $t=p+q-1$ и рассмотрим чёрно-белый граф из $t$ вершин. Если $d_i$ степень $i$-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, $\sum _{i=1}^t{d}_i$ — чётно. Поскольку $t$ нечётно, должно существовать чётное $d_i$. Для определённости положим, что $d_1$ чётно. Обозначим через $M$ и $N$ вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда $|M|=d_1$ и $|N|=t-1-d_1$ оба чётны. Согласно принципу Дирихле (комбинаторика), либо $|M|⩾p-1$, либо $N⩾q$. Так как $|M|$ чётно, а $p-1$ нечётно, первое неравенство можно усилить, так что либо $|M|⩾p$, либо $|N|⩾q$.

Предположим $|M|⩾p=R(r-1,s)$. Тогда либо подграф, порождённый множеством $M$, содержит белый $K_s$ и доказательство завершено, либо он содержит чёрный $K_{r-1}$, который вместе с вершиной 1 образует чёрный $K_r$. Случай $|N|⩾q=R(r,s-1)$ рассматривается аналогично.

Случай большего количества цветов.

Лемма 2. Если $c>2$, то $R(n_1,\dots ,n_c)⩽R(n_1,\dots ,n_{c-2},R(n_{c-1},n_c)).$

Доказательство. Рассмотрим граф из $R(n_1,\dots ,n_{c-2},R(n_{c-1},n_c))$ вершин и окрасим его рёбра $c$ цветами. Будем временно считать цвета $c-1$ и $c$ одним цветом. Тогда граф становится $(c-1)$-цветным. Согласно определению числа $R(n_1,\dots ,n_{c-2},R(n_{c-1},n_c))$, такой граф либо содержит $K_{n_i}$ для некоторого цвета $i$, такого что $1⩽i⩽c-2$ либо $K_{R(n_{c-1},n_c)}$, окрашенный общим цветом $c-1$ и $c$. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный $R(n_{c-1},n_c)$ — вершинный граф содержит либо $K_{n_{c-1}}$ цвета $c-1$, либо $K_{n_c}$ цвета $c$, так что утверждение полностью доказано.

Из леммы 1 следует конечность чисел Рамсея для $c=2$. Отсюда, на основании леммы 2, следует конечность $R(n_1,\dots ,n_c)$ для любого $c$. Это доказывает теорему Рамсея.

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

Таблица значений

Для $N(q_1,q_2,\dots ,q_t;t)$ при $t>2$ имеется очень мало данныхШаблон:Sfn. Следующая таблица значений чисел Рамсея для $N(q_1,q_2;2)$ взята из таблицы Шаблон:Iw, данные приведены по состоянию на 2020 год.

$r,s$	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	[59, 84]	[101, 216]	[134, 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]	[581, 12677]
10	1	10	[40, 42]	[92, 149]	[149, 442]	[204, 1171]	[292, 2826]	[343, 6090]	[581, 12677]	[798, 23556]

Прим: Значения диагональных чисел Рамсея $R(n,n)$ выделены жирным.

Асимптотические оценки

Из неравенства $R(r,s)⩽R(r-1,s)+R(r,s-1)$ вытекает, что

$R(r,s)⩽(\genfrac{}{}{0ex}{}{r+s-2}{r-1}).$

В частности отсюда вытекает верхняя граница полученная Эрдёшем и Секерешем в 1935 году:

$R(s,s)⩽(1+o(1))\frac{4^{s-1}}{\sqrt{\pi s}}.$

Нижняя граница получена Эрдёшем в 1947 году с помощью его вероятностного метода:

$R(s,s)⩾(1+o(1))\frac{s}{\sqrt{2}e}{2}^{s/2},$

Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти $R(5,5)$, но не $R(6,6)$.

Известна также найденная Кимом в 1995 году оценка $R(3,t)⩾(\frac{1}{162}+o(1))\frac{t^2}{\ln t}$. В сочетании с оценкой $R(3,t)⩽(1+o(1))\frac{t^2}{\ln t}$ это неравенство задаёт порядок роста величины $R(3,t)=\mathrm{\Theta }\left(\frac{t^2}{\ln t}\right)$.

В 2023 году Кампос, Гриффитс, Моррис и Сахасрабух улучшили верхнюю границу:

$R(s,s)⩽(4-2^{-7}{)}^s.$

Вариации и обобщения

• Теорема Эрдёша — Радо — обобщение теоремы Рамсея на несчётные множества.

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

Ссылки

• Прасолов В. В. Теорема Рамсея (см. разбор задачи 22.7)
• Теория Рамсея

Литература

• Шаблон:Книга