Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 годуF. P. Ramsey On a problem of formal logic. — «Proc. London Math. Soc.», 2-nd ser., 30 (1930), pp. 264—286. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.
Формулировки
Теоретико-множественная формулировка
Частный случай N(p, q, r) Пусть , и — натуральные числа, причём .
Тогда существует число , обладающее следующим свойством: если все -элементные подмножества -элементного множества произвольным образом разбиты на два непересекающихся семейства и , то либо существует -элементное подмножество множества , все -элементные подмножества которого содержатся в , либо существует -элементное подмножество, все -элементные подмножества которого содержатся в .
Общий случай Пусть множество имеет элементов. Рассмотрим его -подмножества , обозначим совокупность всех этих подмножеств , упорядоченные -разбиения , числа , задающие разбиение .
Тогда для любого упорядоченного -разбиения множества существует такое минимальное число , что если , то существует — подмножество множества , то есть такое -подмножество множества , все -подмножества которого содержатся в .
Формулировка на языке теории графов Для любых натуральных чисел в любой -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с вершинами для некоторого цвета . В частности, для любых и , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из вершин, либо полный белый подграф из вершин.
Числа Рамсея
Минимальное число , при котором это выполнено, называют числом Рамсея.
Например, равенство означает, что с одной стороны в любой двухцветной раскраске полного графа найдётся одноцветный треугольник, а с другой стороны — то, что полный граф допускает двухцветную раскраску без одноцветных треугольников.
В общем случае для -цветной раскраски используется обозначение для минимального числа вершин, обеспечивающего существование для некоторого цвета .
Доказательство теоремы Рамсея
Двухцветный случай Лемма 1.
Доказательство. Докажем с помощью метода математической индукции по .
База индукции. , так как 1-вершинный граф можно считать полным графом любого цвета.
Индукционный переход. Пусть и . Рассмотрим полный чёрно-белый граф из вершин. Возьмём произвольную вершину и обозначим через и множества инцидентные в чёрном и белом подграфе соответственно. Так как в графе вершин, согласно принципу Дирихле (комбинаторика), либо , либо .
Пусть . Тогда либо в (и следовательно во всём графе) есть белый , что завершает доказательство, либо в есть чёрный , который вместе с образует чёрный . Случай рассматривается аналогично.
Замечание. Если и оба чётны, неравенство можно усилить: .
Доказательство. Предположим, и оба чётны. Положим и рассмотрим чёрно-белый граф из вершин. Если степень -й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, — чётно. Поскольку нечётно, должно существовать чётное . Для определённости положим, что чётно. Обозначим через и вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда и оба чётны. Согласно принципу Дирихле (комбинаторика), либо , либо . Так как чётно, а нечётно, первое неравенство можно усилить, так что либо , либо .
Предположим . Тогда либо подграф, порождённый множеством , содержит белый и доказательство завершено, либо он содержит чёрный , который вместе с вершиной 1 образует чёрный . Случай рассматривается аналогично.
Случай большего количества цветов. Лемма 2. Если , то
Доказательство. Рассмотрим граф из вершин и окрасим его рёбра цветами. Будем временно считать цвета и одним цветом. Тогда граф становится -цветным. Согласно определению числа , такой граф либо содержит для некоторого цвета , такого что либо , окрашенный общим цветом и . В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный — вершинный граф содержит либо цвета , либо цвета , так что утверждение полностью доказано.
Из леммы 1 следует конечность чисел Рамсея для . Отсюда, на основании леммы 2, следует конечность для любого . Это доказывает теорему Рамсея.
Значения чисел Рамсея
Таблица значений Для при имеется очень мало данных. Следующая таблица значений чисел Рамсея для взята из таблицы (revision 15), данные приведены по состоянию на 2020 год, но с учетом 2024 года.
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, 41] 4 1 4 9 18 25 [36, 40] [49, 58] [59, 79] [73, 105] [92, 135] 5 1 5 14 25 [43, 46] [59, 85] [80, 133] [101, 193] [133, 282] [149, 381] 6 1 6 18 [36, 40] [59, 85] [102, 160] [115, 270] [134, 423] [183, 651] [204, 944] 7 1 7 23 [49, 58] [80, 133] [115, 270] [205, 492] [219, 832] [252, 1368] [292, 2119] 8 1 8 28 [59, 79] [101, 193] [134, 423] [219, 832] [282, 1518] [329, 2662] [343, 4402] 9 1 9 36 [73, 105] [133, 282] [183, 651] [252, 1368] [329, 2662] [565, 4956] [581, 8675] 10 1 10 [40, 41] [92, 135] [149, 381] [204, 944] [292, 2119] [343, 4402] [581, 8675] [798, 16064] Прим: Значения диагональных чисел Рамсея выделены жирным.
Асимптотические оценки Из неравенства вытекает, что
В частности отсюда вытекает верхняя граница полученная Эрдёшем и Секерешем в 1935 году:
Нижняя граница получена Эрдёшем в 1947 году с помощью его вероятностного метода:
Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти , но не .
Известна также найденная Кимом в 1995 году оценка . В сочетании с оценкой это неравенство задаёт порядок роста величины .
В 2023 году Кампос, Гриффитс, Моррис и Сахасрабух улучшили верхнюю границу:
Вариации и обобщения
Теорема Эрдёша — Радо — обобщение теоремы Рамсея на несчётные множества.
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
Примечания
Ссылки Прасолов В. В. Теорема Рамсея (см. разбор задачи 22.7) Теория Рамсея
Литература
Категория:Теоремы теории множеств Р Категория:Теория Рамсея