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

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

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

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

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

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

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

Общий случай

Пусть множество $S$ имеет $N$ элементов. Рассмотрим его $r$ -подмножества $r\geqslant 1$ , обозначим совокупность всех этих подмножеств $P_{r}(S)$ , упорядоченные $t$ -разбиения $P_{r}(S)=A_{1}\cup A_{2}\cup \ldots \cup A_{t}$ , числа $q_{1},\ q_{2},\ \ldots ,\ q_{t}$ , задающие разбиение $1\leqslant r\leqslant q_{1},\;q_{2},\;\ldots ,\;q_{t}$ .

Тогда для любого упорядоченного $t$ -разбиения множества $P_{r}(S)$ существует такое минимальное число $N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;r)$ , что если $N\geqslant N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;r)$ , то существует $(q_{i},\;A_{i})$ — подмножество множества $S$ , то есть такое $q_{i}$ -подмножество множества $S$ , все $r$ -подмножества которого содержатся в $A_{i},\ 1\leqslant t\leqslant t$ ^[2].

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

Для любых $c$ натуральных чисел $n_{1},\ n_{2},\ \ldots ,\ 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},\;\ldots ,\;n_{c})$ для минимального числа вершин, обеспечивающего существование $K_{n_{i}}$ для некоторого цвета $i$ .

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

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

Лемма 1. $R(r,\;s)\leqslant 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|\geqslant R(r-1,\;s)$ , либо $|N|\geqslant R(r,\;s-1)$ .

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

Замечание. Если $R(r-1,\;s)$ и $R(r,\;s-1)$ оба чётны, неравенство можно усилить: $R(r,\;s)\leqslant 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|\geqslant p-1$ , либо $N\geqslant q$ . Так как $|M|$ чётно, а $p-1$ нечётно, первое неравенство можно усилить, так что либо $|M|\geqslant p$ , либо $|N|\geqslant q$ .

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

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

Лемма 2. Если $c>2$ , то $R(n_{1},\;\ldots ,\;n_{c})\leqslant R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c})).$

Доказательство. Рассмотрим граф из $R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ вершин и окрасим его рёбра $c$ цветами. Будем временно считать цвета $c-1$ и $c$ одним цветом. Тогда граф становится $(c-1)$ -цветным. Согласно определению числа $R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ , такой граф либо содержит $K_{n_{i}}$ для некоторого цвета $i$ , такого что $1\leqslant i\leqslant 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},\;\ldots ,\;n_{c})$ для любого $c$ . Это доказывает теорему Рамсея.

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

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

Для $N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;t)$ при $t>2$ имеется очень мало данных^[3]. Следующая таблица значений чисел Рамсея для $N(q_{1},\;q_{2};\;2)$ взята из таблицы Радзишевского^[англ.]^[4], данные приведены по состоянию на 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)\leqslant R(r-1,\;s)+R(r,\;s-1)$ вытекает, что

R(r,\;s)\leqslant {\binom {r+s-2}{r-1}}.

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

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

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

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

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

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

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

R(s,\;s)\leqslant (4-2^{-7})^{s}.

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

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

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

Примечания

↑ F. P. Ramsey On a problem of formal logic. — «Proc. London Math. Soc.», 2-nd ser., 30 (1930), pp. 264—286
↑ Рыбников, 1972, с. 93.
↑ Рыбников, 1972, с. 96.
↑ Stanisław Radziszowski. Small Ramsey Numbers (англ.) // The Electronic Journal of Combinatorics. — 2017. — 3 March. — ISSN 1077-8926. Архивировано 29 мая 2017 года. (revision 15)
↑ Campos, Marcelo; Griffiths, Simon; Morris, Robert; Sahasrabudhe, Julian (2023-03-16). "An exponential improvement for diagonal Ramsey". arXiv:2303.09521 [math.CO]. Архивировано 24 марта 2023. Дата обращения: 22 марта 2023. {{cite journal}}: Неизвестный параметр |deadlink= игнорируется (|url-status= предлагается) (справка)

Ссылки

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

Литература

Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.

[1] F. P. Ramsey On a problem of formal logic. — «Proc. London Math. Soc.», 2-nd ser., 30 (1930), pp. 264—286

[_4c7d9f7a31341a6a-2] Рыбников, 1972, с. 93.

[_4c7d9f7a31341a6f-3] Рыбников, 1972, с. 96.

[4] Stanisław Radziszowski. Small Ramsey Numbers (англ.) // The Electronic Journal of Combinatorics. — 2017. — 3 March. — ISSN 1077-8926. Архивировано 29 мая 2017 года. (revision 15)

[5] Campos, Marcelo; Griffiths, Simon; Morris, Robert; Sahasrabudhe, Julian (2023-03-16). "An exponential improvement for diagonal Ramsey". arXiv:2303.09521 [math.CO]. Архивировано 24 марта 2023. Дата обращения: 22 марта 2023. {{cite journal}}: Неизвестный параметр |deadlink= игнорируется (|url-status= предлагается) (справка)

[1]

[2]

[3]

[4]

[5]