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

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

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

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

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

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


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

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


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

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


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

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

Следующая таблица значений чисел Рамсея частично взята из таблицы Радзишовского,[1] кроме R(4,6) ≥ 36, что доказано Джоффри Икзу (Exoo) в 2012 году,[2] и R(3,10) ≤ 42, что доказано Яном Гёдгебером (Goedgebeur) и Станиславом Радзишовским в 2012 году.[3] Новую нижнюю границу для R(4,8) смотри: 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

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

Из неравенства R(r, s) ≤ R(r − 1, s) + R(r, s − 1) вытекает, что

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

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

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

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

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

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

Известна также найденная Кимом в 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 

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