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

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

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

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

Пусть , и  — натуральные числа, причём .

Тогда существует число , обладающее следующим свойством: если все -элементные подмножества -элементного множества произвольным образом разбиты на два непересекающихся семейства и , то либо существует -элементное подмножество множества , все -элементные подмножества которого содержатся в , либо существует -элементное подмножество, все -элементные подмножества которого содержатся в .

Общий случай

Пусть множество имеет элементов. Рассмотрим его -подмножества , обозначим совокупность всех этих подмножеств , упорядоченные -разбиения , числа , задающие разбиение .

Тогда для любого упорядоченного -разбиения множества существует такое минимальное число , что если , то существует  — подмножество множества , то есть такое  — подмножество множества , все -подмножества которого содержатся в [2].

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

Для любых натуральных чисел в любой -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с вершинами для некоторого цвета . В частности, для любых и , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из вершин, либо полный белый подграф из вершин.

Числа Рамсея

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

Минимальное число , при котором это выполнено, называют числом Рамсея.

Например, равенство означает, что с одной стороны в любой двухцветной раскраске полного графа найдётся одноцветный треугольник, а с другой стороны — то, что полный граф допускает двухцветную раскраску без одноцветных треугольников.

В общем случае для -цветной раскраски используется обозначение для минимального числа вершин, обеспечивающего существование для некоторого цвета .

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

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

Лемма 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]

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

Из неравенства вытекает, что

В частности отсюда вытекает верхняя граница (Эрдёш, Секереш)

Нижняя граница

получена Эрдёшем в 1947 году с помощью его вероятностного метода.

Современные оценки получены Спенсером и Конлоном соответственно.

Очевидно, что эти оценки незначительно улучшают первые результаты и не близки между собой.

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

Известна также найденная Кимом в 1995 году оценка . В сочетании с оценкой это неравенство задаёт порядок роста величины .

См. также

Примечания

  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. (revision 15)

Ссылки

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.