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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формулировки[править | править вики-текст]

Теоретико-множественная формулировка[править | править вики-текст]

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

Частный случай[править | править вики-текст]

При теорему удобно формулировать на языке теории графов:

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

Числа Рамсея[править | править вики-текст]

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

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

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

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

Таблица значений[править | править вики-текст]

Следующая таблица значений чисел Рамсея взята из таблицы Радзишевского[en][1].

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 [56, 84] [101, 216] [127, 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] [580, 12677]
10 1 10 [40, 42] [92, 149] [149, 442] [179, 1171] [289, 2826] [343, 6090] [581, 12677] [798, 23556]

Асимптотические оценки[править | править вики-текст]

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

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

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

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

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

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Stanisław Radziszowski Small Ramsey Numbers (англ.) // The Electronic Journal of Combinatorics. — 2017. — 3 March. — ISSN 1077-8926. (revision 15)

Ссылки[править | править вики-текст]