Теорема Рамсея
—
теорема
комбинаторики
о разбиениях множеств, сформулированная и доказанная английским математиком
Фрэнком Рамсеем
в 1930 году
. Встречается в литературе в разных формулировках. Эта теорема положила начало
теории Рамсея
.
Тогда существует число
, обладающее следующим свойством: если все
-элементные подмножества
-элементного
множества
произвольным образом разбиты на два непересекающихся семейства
и
, то либо существует
-элементное подмножество множества
, все
-элементные подмножества которого содержатся в
, либо существует
-элементное подмножество, все
-элементные подмножества которого содержатся в
.
Общий случай
Пусть множество
имеет
элементов. Рассмотрим его
-подмножества
, обозначим совокупность всех этих подмножеств
, упорядоченные
-разбиения
, числа
, задающие разбиение
.
Тогда для любого упорядоченного
-разбиения множества
существует такое минимальное число
, что если
, то существует
— подмножество множества
, то есть такое
— подмножество множества
, все
-подмножества которого содержатся в
.
Формулировка на языке теории графов
Для любых
натуральных чисел
в любой
-цветной раскраске рёбер достаточно большого
полного графа
содержится полный подграф с
вершинами для некоторого цвета
. В частности, для любых
и
, достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из
вершин, либо полный белый подграф из
вершин.
Числа Рамсея
Минимальное число
, при котором это выполнено, называют числом Рамсея.
Например, равенство
означает, что с одной стороны в любой двухцветной раскраске полного графа
найдётся одноцветный треугольник, а с другой стороны — то, что полный граф
допускает двухцветную раскраску без одноцветных треугольников.
В общем случае для
-цветной раскраски используется обозначение
для минимального числа вершин, обеспечивающего существование
для некоторого цвета
.
База индукции.
, так как 1-вершинный граф можно считать полным графом любого цвета.
Индукционный переход
. Пусть
и
. Рассмотрим полный чёрно-белый граф из
вершин. Возьмём произвольную вершину
и обозначим через
и
множества инцидентные
в чёрном и белом подграфе соответственно. Так как в графе
вершин, согласно
принципу Дирихле (комбинаторика)
, либо
, либо
.
Пусть
. Тогда либо в
(и следовательно во всём графе) есть белый
, что завершает доказательство, либо в
есть чёрный
, который вместе с
образует чёрный
. Случай
рассматривается аналогично.
Замечание.
Если
и
оба чётны, неравенство можно усилить:
.
Доказательство
. Предположим,
и
оба чётны. Положим
и рассмотрим чёрно-белый граф из
вершин. Если
степень
-й вершины в чёрном подграфе, то, согласно
лемме о рукопожатиях
,
— чётно. Поскольку
нечётно, должно существовать чётное
. Для определённости положим, что
чётно. Обозначим через
и
вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда
и
оба чётны. Согласно
принципу Дирихле (комбинаторика)
, либо
, либо
. Так как
чётно, а
нечётно, первое неравенство можно усилить, так что либо
, либо
.
Предположим
. Тогда либо подграф, порождённый множеством
, содержит белый
и доказательство завершено, либо он содержит чёрный
, который вместе с вершиной 1 образует чёрный
. Случай
рассматривается аналогично.
Случай большего количества цветов.
Лемма 2.
Если
, то
Доказательство.
Рассмотрим граф из
вершин и окрасим его рёбра
цветами. Будем временно считать цвета
и
одним цветом. Тогда граф становится
-цветным. Согласно определению числа
, такой граф либо содержит
для некоторого цвета
, такого что
либо
, окрашенный общим цветом
и
. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный
— вершинный граф содержит либо
цвета
, либо
цвета
, так что утверждение полностью доказано.
Из леммы 1 следует конечность чисел Рамсея для
. Отсюда, на основании леммы 2, следует конечность
для любого
. Это доказывает теорему Рамсея.
Значения чисел Рамсея
Таблица значений
Для
при
имеется очень мало данных
. Следующая таблица значений чисел Рамсея для
взята из таблицы
, данные приведены по состоянию на 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 году:
Теория Рамсея
— раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
Примечания
F. P. Ramsey
On a problem of formal logic. — «Proc. London Math. Soc.», 2-nd ser., 30 (1930), pp. 264—286
, с. 93.
, с. 96.
Stanisław Radziszowski.
(англ.)
// The Electronic Journal of Combinatorics. — 2017. — 3 March. —
ISSN
.
29 мая 2017 года.
(revision 15)
Campos, Marcelo; Griffiths, Simon; Morris, Robert; Sahasrabudhe, Julian (2023-03-16).
.
arXiv:2303.09521 [math.CO]
.
из оригинала
24 марта 2023
. Дата обращения:
22 марта 2023
.
{{
cite journal
}}
:
Неизвестный параметр
|deadlink=
игнорируется (
|url-status=
предлагается) (
справка
)