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

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

Теорема

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

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

См. также

• Теория Рамсея‎

Ссылки

• Теорема Рамсея нерабочая
• Теория Рамсея