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

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

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

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

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

Пусть 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), при котором это выполняется называется числом Рамсея, то есть:

R(s,t) = \min \{n \mid \forall G(V,E): |V|=n \Rightarrow  \omega (G)\geqslant s \or \alpha (G)\geqslant t\}.


Здесь G(V,E) — граф G с множеством вершин V и множеством ребер E, \omega(G)кликовое число графа G, а \alpha(G) — независимое число графа G.

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

Следующая таблица значений чисел Рамсея частично взята из таблицы Радзишовского,[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).

Известна также найденная Кимом в 1995 году оценка R(3,t) \geq (\frac{1}{162}+o(1))\frac{t^2}{\ln{t}}. В сочетании с оценкой R(3,t) \leq (1+o(1))\frac{t^2}{\ln{t}} это неравенство задаёт порядок роста величины R(3,t)=O(\frac{t^2}{\ln{t}})

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

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

  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 

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