Теорема Рамсея (Mykjybg Jgbvyx)
Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году[1]. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
Формулировки
[править | править код]Теоретико-множественная формулировка
[править | править код]Частный случай N(p, q, r)
[править | править код]Пусть , и — натуральные числа, причём .
Тогда существует число , обладающее следующим свойством: если все -элементные подмножества -элементного множества произвольным образом разбиты на два непересекающихся семейства и , то либо существует -элементное подмножество множества , все -элементные подмножества которого содержатся в , либо существует -элементное подмножество, все -элементные подмножества которого содержатся в .
Общий случай
[править | править код]Пусть множество имеет элементов. Рассмотрим его -подмножества , обозначим совокупность всех этих подмножеств , упорядоченные -разбиения , числа , задающие разбиение .
Тогда для любого упорядоченного -разбиения множества существует такое минимальное число , что если , то существует — подмножество множества , то есть такое — подмножество множества , все -подмножества которого содержатся в [2].
Формулировка на языке теории графов
[править | править код]Для любых натуральных чисел в любой -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с вершинами для некоторого цвета . В частности, для любых и , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из вершин, либо полный белый подграф из вершин.
Числа Рамсея
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/98/RamseyTheory_K5_no_mono_K3.svg/210px-RamseyTheory_K5_no_mono_K3.svg.png)
Минимальное число , при котором это выполнено, называют числом Рамсея.
Например, равенство означает, что с одной стороны в любой двухцветной раскраске полного графа найдётся одноцветный треугольник, а с другой стороны — то, что полный граф допускает двухцветную раскраску без одноцветных треугольников.
В общем случае для -цветной раскраски используется обозначение для минимального числа вершин, обеспечивающего существование для некоторого цвета .
Доказательство теоремы Рамсея
[править | править код]Двухцветный случай
[править | править код]Лемма 1.
Доказательство. Докажем с помощью метода математической индукции по .
База индукции. , так как 1-вершинный граф можно считать полным графом любого цвета.
Индукционный переход. Пусть и . Рассмотрим полный чёрно-белый граф из вершин. Возьмём произвольную вершину и обозначим через и множества инцидентные в чёрном и белом подграфе соответственно. Так как в графе вершин, согласно принципу Дирихле (комбинаторика), либо , либо .
Пусть . Тогда либо в (и следовательно во всём графе) есть белый , что завершает доказательство, либо в есть чёрный , который вместе с образует чёрный . Случай рассматривается аналогично.
Замечание. Если и оба чётны, неравенство можно усилить: .
Доказательство. Предположим, и оба чётны. Положим и рассмотрим чёрно-белый граф из вершин. Если степень -й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, — чётно. Поскольку нечётно, должно существовать чётное . Для определённости положим, что чётно. Обозначим через и вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда и оба чётны. Согласно принципу Дирихле (комбинаторика), либо , либо . Так как чётно, а нечётно, первое неравенство можно усилить, так что либо , либо .
Предположим . Тогда либо подграф, порождённый множеством , содержит белый и доказательство завершено, либо он содержит чёрный , который вместе с вершиной 1 образует чёрный . Случай рассматривается аналогично.
Случай большего количества цветов.
[править | править код]Лемма 2. Если , то
Доказательство. Рассмотрим граф из вершин и окрасим его рёбра цветами. Будем временно считать цвета и одним цветом. Тогда граф становится -цветным. Согласно определению числа , такой граф либо содержит для некоторого цвета , такого что либо , окрашенный общим цветом и . В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный — вершинный граф содержит либо цвета , либо цвета , так что утверждение полностью доказано.
Из леммы 1 следует конечность чисел Рамсея для . Отсюда, на основании леммы 2, следует конечность для любого . Это доказывает теорему Рамсея.
Значения чисел Рамсея
[править | править код]Таблица значений
[править | править код]Для при имеется очень мало данных[3]. Следующая таблица значений чисел Рамсея для взята из таблицы Радзишевского[англ.][4], данные приведены по состоянию на 2020 год.
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] |
Прим: Значения диагональных чисел Рамсея выделены жирным.
Асимптотические оценки
[править | править код]Из неравенства вытекает, что
В частности отсюда вытекает верхняя граница полученная Эрдёшем и Секерешем в 1935 году:
Нижняя граница получена Эрдёшем в 1947 году с помощью его вероятностного метода:
Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти , но не .
Известна также найденная Кимом в 1995 году оценка . В сочетании с оценкой это неравенство задаёт порядок роста величины .
В 2023 году Кампос, Гриффитс, Моррис и Сахасрабух улучшили верхнюю границу[5]:
Вариации и обобщения
[править | править код]- Теорема Эрдёша — Радо — обобщение теоремы Рамсея на несчётные множества.
- Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
Примечания
[править | править код]- ↑ 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.