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

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

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

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

Теоретико-множественная формулировка:

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


Частный случай теоремы (для , ) удобно формулировать на языке теории графов:

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


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

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


Здесь  — граф с множеством вершин и множеством ребер ,  — кликовое число графа , а  — независимое число графа .

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

Следующая таблица значений чисел Рамсея частично взята из таблицы Радзишовского,[1] кроме , что доказано Джоффри Икзу (Exoo) в 2012 году,[2] и , что доказано Яном Гёдгебером (Goedgebeur) и Станиславом Радзишовским в 2012 году.[3] Новую нижнюю границу для смотри: arxiv:1212.1328.

r, s 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 58 — 84 73 — 115 92 — 149
5 1 5 14 25 43 — 49 58 — 87 80 — 143 101 — 216 126 — 316 144 — 442
6 1 6 18 36 — 41 58 — 87 102 — 165 113 — 298 132 — 495 169 — 780 179 — 1171
7 1 7 23 49 — 61 80 — 143 113 — 298 205 — 540 217 — 1031 241 — 1713 289 — 2826
8 1 8 28 58 — 84 101 — 216 132 — 495 217 — 1031 282 — 1870 317 — 3583 331 — 6090
9 1 9 36 73 — 115 126 — 316 169 — 780 241 — 1713 317 — 3583 565 — 6588 581 — 12677
10 1 10 40 — 42 92 — 149 144 — 442 179 — 1171 289 — 2826 331 — 6090 581 — 12677 798 — 23556

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

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

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

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

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

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

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

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

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

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

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

  1. Dynamic Surveys.
  2. B. McKay, Ramsey Graphs
  3. Goedgebeur, Jan & Radziszowski, Stanisław (2012), "New computational upper bounds for Ramsey numbers R(3, k)", arΧiv:1210.5826 

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