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

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

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

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

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

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

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

Общий случай

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

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

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

Для любых ${\displaystyle c}$ натуральных чисел ${\displaystyle n_{1},\ n_{2},\ \ldots ,\ n_{c}}$ в любой ${\displaystyle c}$-цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с ${\displaystyle n_{i}}$ вершинами для некоторого цвета ${\displaystyle i}$. В частности, для любых ${\displaystyle r}$ и ${\displaystyle s}$, достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из ${\displaystyle r}$ вершин, либо полный белый подграф из ${\displaystyle s}$ вершин.

Числа Рамсея

Двухцветная раскраска ${\displaystyle K_{5}}$ без одноцветных треугольников.

Минимальное число ${\displaystyle R(r,\;s)}$, при котором это выполнено, называют числом Рамсея.

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

В общем случае для ${\displaystyle c}$-цветной раскраски используется обозначение ${\displaystyle R(n_{1},\;n_{2},\;\ldots ,\;n_{c})}$ для минимального числа вершин, обеспечивающего существование ${\displaystyle K_{n_{i}}}$ для некоторого цвета ${\displaystyle i}$.

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

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

Лемма 1. ${\displaystyle R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1).}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Для ${\displaystyle N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;t)}$ при ${\displaystyle t>2}$ имеется очень мало данных[3]. Следующая таблица значений чисел Рамсея для ${\displaystyle N(q_{1},\;q_{2};\;2)}$ взята из таблицы Радзишевского^[англ.][4], данные приведены по состоянию на 2020 год.

${\displaystyle 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]

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

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

Из неравенства ${\displaystyle R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)}$ вытекает, что

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. F. P. Ramsey On a problem of formal logic. — «Proc. London Math. Soc.», 2-nd ser., 30 (1930), pp. 264—286
2. Рыбников, 1972, с. 93.
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 (16 марта 2023). "An exponential improvement for diagonal Ramsey". arXiv:2303.09521 [math.CO]. Архивировано 24 марта 2023. Дата обращения: 22 марта 2023.

Ссылки

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

Литература

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