Теорема Рамсея
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году[1]. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
Формулировки
Теоретико-множественная формулировка
Частный случай N(p, q, r)
Пусть [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] и [math]\displaystyle{ r }[/math] — натуральные числа, причём [math]\displaystyle{ p,\;q\geqslant r }[/math].
Тогда существует число [math]\displaystyle{ N=N(p,\;q,\;r) }[/math], обладающее следующим свойством: если все [math]\displaystyle{ r }[/math]-элементные подмножества [math]\displaystyle{ N }[/math]-элементного множества [math]\displaystyle{ S }[/math] произвольным образом разбиты на два непересекающихся семейства [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math], то либо существует [math]\displaystyle{ p }[/math]-элементное подмножество множества [math]\displaystyle{ S }[/math], все [math]\displaystyle{ r }[/math]-элементные подмножества которого содержатся в [math]\displaystyle{ \alpha }[/math], либо существует [math]\displaystyle{ q }[/math]-элементное подмножество, все [math]\displaystyle{ r }[/math]-элементные подмножества которого содержатся в [math]\displaystyle{ \beta }[/math].
Общий случай
Пусть множество [math]\displaystyle{ S }[/math] имеет [math]\displaystyle{ N }[/math] элементов. Рассмотрим его [math]\displaystyle{ r }[/math]-подмножества [math]\displaystyle{ r \geqslant 1 }[/math], обозначим совокупность всех этих подмножеств [math]\displaystyle{ P_{r}(S) }[/math], упорядоченные [math]\displaystyle{ t }[/math]-разбиения [math]\displaystyle{ P_{r}(S) = A_{1} \cup A_{2} \cup \ldots \cup A_{t} }[/math], числа [math]\displaystyle{ q_{1},\ q_{2},\ \ldots,\ q_{t} }[/math], задающие разбиение [math]\displaystyle{ 1 \leqslant r \leqslant q_{1},\; q_{2},\;\ldots,\; q_{t} }[/math].
Тогда для любого упорядоченного [math]\displaystyle{ t }[/math]-разбиения множества [math]\displaystyle{ P_{r}(S) }[/math] существует такое минимальное число [math]\displaystyle{ N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;r) }[/math], что если [math]\displaystyle{ N \geqslant N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;r) }[/math], то существует [math]\displaystyle{ (q_{i},\;A_{i}) }[/math] — подмножество множества [math]\displaystyle{ S }[/math], то есть такое [math]\displaystyle{ q_{i} }[/math] — подмножество множества [math]\displaystyle{ S }[/math], все [math]\displaystyle{ r }[/math]-подмножества которого содержатся в [math]\displaystyle{ A_{i},\ 1 \leqslant t \leqslant t }[/math][2].
Формулировка на языке теории графов
Для любых [math]\displaystyle{ c }[/math] натуральных чисел [math]\displaystyle{ n_1,\ n_2,\ \ldots,\ n_c }[/math] в любой [math]\displaystyle{ c }[/math]-цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с [math]\displaystyle{ n_i }[/math] вершинами для некоторого цвета [math]\displaystyle{ i }[/math]. В частности, для любых [math]\displaystyle{ r }[/math] и [math]\displaystyle{ s }[/math], достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из [math]\displaystyle{ r }[/math] вершин, либо полный белый подграф из [math]\displaystyle{ s }[/math] вершин.
Числа Рамсея
Минимальное число [math]\displaystyle{ R(r,\;s) }[/math], при котором это выполнено, называют числом Рамсея.
Например, равенство [math]\displaystyle{ R(3,\;3)=6 }[/math] означает, что с одной стороны в любой двухцветной раскраске полного графа [math]\displaystyle{ K_6 }[/math] найдётся одноцветный треугольник, а с другой стороны — то, что полный граф [math]\displaystyle{ K_5 }[/math] допускает двухцветную раскраску без одноцветных треугольников.
В общем случае для [math]\displaystyle{ c }[/math]-цветной раскраски используется обозначение [math]\displaystyle{ R(n_1,\;n_2,\;\ldots,\;n_c) }[/math] для минимального числа вершин, обеспечивающего существование [math]\displaystyle{ K_{n_i} }[/math] для некоторого цвета [math]\displaystyle{ i }[/math].
Доказательство теоремы Рамсея
Двухцветный случай
Лемма 1. [math]\displaystyle{ R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1). }[/math]
Доказательство. Докажем с помощью метода математической индукции по [math]\displaystyle{ r+s }[/math].
База индукции. [math]\displaystyle{ R(n,\;1) = R(1,\;n) = 1 }[/math], так как 1-вершинный граф можно считать полным графом любого цвета.
Индукционный переход. Пусть [math]\displaystyle{ r\gt 1 }[/math] и [math]\displaystyle{ s\gt 1 }[/math]. Рассмотрим полный чёрно-белый граф из [math]\displaystyle{ R(r-1,\;s)+R(r,\;s-1) }[/math] вершин. Возьмём произвольную вершину [math]\displaystyle{ v }[/math] и обозначим через [math]\displaystyle{ M }[/math] и [math]\displaystyle{ N }[/math] множества инцидентные [math]\displaystyle{ v }[/math] в чёрном и белом подграфе соответственно. Так как в графе [math]\displaystyle{ R(r-1,\;s)+R(r,\;s-1)=|M|+|N|+1 }[/math] вершин, согласно принципу Дирихле (комбинаторика), либо [math]\displaystyle{ |M|\geqslant R(r-1,\;s) }[/math], либо [math]\displaystyle{ |N|\geqslant R(r,\;s-1) }[/math].
Пусть [math]\displaystyle{ |M|\geqslant R(r-1,\;s) }[/math]. Тогда либо в [math]\displaystyle{ M }[/math] (и следовательно во всём графе) есть белый [math]\displaystyle{ K_s }[/math], что завершает доказательство, либо в [math]\displaystyle{ M }[/math] есть чёрный [math]\displaystyle{ K_{r-1} }[/math], который вместе с [math]\displaystyle{ v }[/math] образует чёрный [math]\displaystyle{ K_r }[/math]. Случай [math]\displaystyle{ |N|\geqslant R(r,\;s-1) }[/math] рассматривается аналогично.
Замечание. Если [math]\displaystyle{ R(r-1,\;s) }[/math] и [math]\displaystyle{ R(r,\;s-1) }[/math] оба чётны, неравенство можно усилить: [math]\displaystyle{ R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)-1 }[/math].
Доказательство. Предположим, [math]\displaystyle{ p=R(r-1,\;s) }[/math] и [math]\displaystyle{ q=R(r,\;s-1) }[/math] оба чётны. Положим [math]\displaystyle{ t=p+q-1 }[/math] и рассмотрим чёрно-белый граф из [math]\displaystyle{ t }[/math] вершин. Если [math]\displaystyle{ d_i }[/math] степень [math]\displaystyle{ i }[/math]-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, [math]\displaystyle{ \sum_{i=1}^t d_i }[/math] — чётно. Поскольку [math]\displaystyle{ t }[/math] нечётно, должно существовать чётное [math]\displaystyle{ d_i }[/math]. Для определённости положим, что [math]\displaystyle{ d_1 }[/math] чётно. Обозначим через [math]\displaystyle{ M }[/math] и [math]\displaystyle{ N }[/math] вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда [math]\displaystyle{ |M|=d_1 }[/math] и [math]\displaystyle{ |N|=t-1-d_1 }[/math] оба чётны. Согласно принципу Дирихле (комбинаторика), либо [math]\displaystyle{ |M|\geqslant p-1 }[/math], либо [math]\displaystyle{ N\geqslant q }[/math]. Так как [math]\displaystyle{ |M| }[/math] чётно, а [math]\displaystyle{ p-1 }[/math] нечётно, первое неравенство можно усилить, так что либо [math]\displaystyle{ |M|\geqslant p }[/math], либо [math]\displaystyle{ |N|\geqslant q }[/math].
Предположим [math]\displaystyle{ |M|\geqslant p=R(r-1,\;s) }[/math]. Тогда либо подграф, порождённый множеством [math]\displaystyle{ M }[/math], содержит белый [math]\displaystyle{ K_s }[/math] и доказательство завершено, либо он содержит чёрный [math]\displaystyle{ K_{r-1} }[/math], который вместе с вершиной 1 образует чёрный [math]\displaystyle{ K_r }[/math]. Случай [math]\displaystyle{ |N|\geqslant q=R(r,\;s-1) }[/math] рассматривается аналогично.
Случай большего количества цветов.
Лемма 2. Если [math]\displaystyle{ c\gt 2 }[/math], то [math]\displaystyle{ R(n_1,\;\ldots,\;n_c)\leqslant R(n_1,\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_c)). }[/math]
Доказательство. Рассмотрим граф из [math]\displaystyle{ R(n_1,\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_c)) }[/math] вершин и окрасим его рёбра [math]\displaystyle{ c }[/math] цветами. Будем временно считать цвета [math]\displaystyle{ c-1 }[/math] и [math]\displaystyle{ c }[/math] одним цветом. Тогда граф становится [math]\displaystyle{ (c-1) }[/math]-цветным. Согласно определению числа [math]\displaystyle{ R(n_1,\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_c)) }[/math], такой граф либо содержит [math]\displaystyle{ K_{n_i} }[/math] для некоторого цвета [math]\displaystyle{ i }[/math], такого что [math]\displaystyle{ 1\leqslant i\leqslant c-2 }[/math] либо [math]\displaystyle{ K_{R(n_{c-1},\;n_c)} }[/math], окрашенный общим цветом [math]\displaystyle{ c-1 }[/math] и [math]\displaystyle{ c }[/math]. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный [math]\displaystyle{ R(n_{c-1},\;n_c) }[/math] — вершинный граф содержит либо [math]\displaystyle{ K_{n_{c-1}} }[/math] цвета [math]\displaystyle{ c-1 }[/math], либо [math]\displaystyle{ K_{n_c} }[/math] цвета [math]\displaystyle{ c }[/math], так что утверждение полностью доказано.
Из леммы 1 следует конечность чисел Рамсея для [math]\displaystyle{ c=2 }[/math]. Отсюда, на основании леммы 2, следует конечность [math]\displaystyle{ R(n_1,\;\ldots,\;n_c) }[/math] для любого [math]\displaystyle{ c }[/math]. Это доказывает теорему Рамсея.
Значения чисел Рамсея
Таблица значений
Для [math]\displaystyle{ N(q_{1},\;q_{2},\;\ldots,\;q_{t};\;t) }[/math] при [math]\displaystyle{ t \gt 2 }[/math] имеется очень мало данных[3]. Следующая таблица значений чисел Рамсея для [math]\displaystyle{ N(q_{1},\;q_{2};\;2) }[/math] взята из таблицы Радзишевского[4], данные приведены по состоянию на 2020 год.
[math]\displaystyle{ r,\ s }[/math] | 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] |
Асимптотические оценки
Из неравенства [math]\displaystyle{ R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1) }[/math] вытекает, что
- [math]\displaystyle{ R(r,\;s)\leqslant\binom{r+s-2}{r-1}. }[/math]
В частности отсюда вытекает верхняя граница (Эрдёш, Секереш)
- [math]\displaystyle{ R(s,\;s)\leqslant(1+o(1))\frac{4^{s-1}}{\sqrt{\pi s}}. }[/math]
Нижняя граница
- [math]\displaystyle{ R(s,\;s)\geqslant(1+o(1))\frac{s}{\sqrt{2}e}2^{s/2}, }[/math]
получена Эрдёшем в 1947 году с помощью его вероятностного метода.
Современные оценки получены Спенсером и Конлоном соответственно.
- [math]\displaystyle{ (1+o(1))\frac{\sqrt{2}s}{e}2^{s/2}\leqslant R(s,\;s)\leqslant s^{-c\log s/\log\log s}4^{s}. }[/math]
Очевидно, что эти оценки незначительно улучшают первые результаты и не близки между собой.
Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти [math]\displaystyle{ R(5,\;5) }[/math], но не [math]\displaystyle{ R(6,\;6) }[/math].
Известна также найденная Кимом в 1995 году оценка [math]\displaystyle{ R(3,\;t)\geqslant\left(\frac{1}{162}+o(1)\right)\frac{t^2}{\ln{t}} }[/math]. В сочетании с оценкой [math]\displaystyle{ R(3,\;t)\leqslant(1+o(1))\frac{t^2}{\ln{t}} }[/math] это неравенство задаёт порядок роста величины [math]\displaystyle{ R(3,\;t)=\Theta\left(\frac{t^2}{\ln{t}}\right) }[/math].
Вариации и обобщения
- Теорема Эрдёша — Радо — обобщениние теоремы Рамсея на несчётные множества.
- Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
Примечания
- ↑ 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)
Ссылки
- Прасолов В. В. Теорема Рамсея (см. разбор задачи 22.7)
- Теория Рамсея
Литература
- Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.