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

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

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

Теорема[править | править исходный текст]

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

Пусть p, q и r — натуральные числа, причем p,\;q\geqslant r. Тогда существует число N=N(p,\;q,\;r), обладающее следующим свойством: если все r-элементные подмножества N-элементного множества S произвольным образом разбиты на два непересекающихся семейства \alpha и \beta, то либо существует p-элементное подмножество множества S, все r-элементные подмножества которого содержатся в \alpha, либо существует q-элементное подмножество, все r-элементные подмножества которого содержатся в \beta.


Формулировка на языке теории графов (более краткая и удобная)

Для любых натуральных чисел 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) вытекает, что

R(r,s) \leq \binom{r+s-2}{r-1}.

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

R(s,s) \leq (1 + o(1))\frac{4^{s-1}}{\sqrt{\pi s}}.

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

R(s,s) \geq (1 + o(1)) \frac{s}{\sqrt{2} e} 2^{s/2},

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

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

(1 + o(1)) \frac{\sqrt{2} s}{e} 2^{s/2} \leq R(s,s) \leq s^{-c \log s/\log \log s} 4^{s},

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

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

Примечания[править | править исходный текст]

  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 

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]