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

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

ФормулировкиПравить

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

Частный случай N(p, q, r)Править

Пусть $p$$p$ , $q$$q$  и $r$$r$  — натуральные числа, причём $p,q⩾<!--\; ⩾\; -->r$$p,\;q\geqslant r$ .

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

Общий случайПравить

Пусть множество $S$$S$  имеет $N$$N$  элементов. Рассмотрим его $r$$r$ -подмножества $r⩾<!--\; ⩾\; -->1$$r\geqslant 1$ , обозначим совокупность всех этих подмножеств $P_r(S)$$P_{r}(S)$ , упорядоченные $t$$t$ -разбиения $P_r(S)=A_1\cup <!--\; \cup \; -->A_2\cup <!--\; \cup \; -->\dots <!--\; \dots \; -->\cup <!--\; \cup \; -->A_t$$P_{r}(S)=A_{1}\cup A_{2}\cup \ldots \cup A_{t}$ , числа $q_1,q_2,\dots <!--\; \dots \; -->,q_t$$q_{1},\ q_{2},\ \ldots ,\ q_{t}$ , задающие разбиение $1⩽<!--\; ⩽\; -->r⩽<!--\; ⩽\; -->q_1,q_2,\dots <!--\; \dots \; -->,q_t$$1\leqslant r\leqslant q_{1},\;q_{2},\;\ldots ,\;q_{t}$ .

Тогда для любого упорядоченного $t$$t$ -разбиения множества $P_r(S)$$P_{r}(S)$  существует такое минимальное число $N(q_1,q_2,\dots <!--\; \dots \; -->,q_t;r)$$N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;r)$ , что если $N⩾<!--\; ⩾\; -->N(q_1,q_2,\dots <!--\; \dots \; -->,q_t;r)$$N\geqslant N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;r)$ , то существует $(q_i,A_i)$$(q_{i},\;A_{i})$  — подмножество множества $S$$S$ , то есть такое $q_i$$q_{i}$  — подмножество множества $S$$S$ , все $r$$r$ -подмножества которого содержатся в $A_i,1⩽<!--\; ⩽\; -->t⩽<!--\; ⩽\; -->t$$A_{i},\ 1\leqslant t\leqslant t$ .

Формулировка на языке теории графовПравить

Для любых $c$$c$  натуральных чисел $n_1,n_2,\dots <!--\; \dots \; -->,n_c$$n_{1},\ n_{2},\ \ldots ,\ n_{c}$  в любой $c$$c$ -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с $n_i$$n_{i}$  вершинами для некоторого цвета $i$$i$ . В частности, для любых $r$$r$  и $s$$s$ , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из $r$$r$  вершин, либо полный белый подграф из $s$$s$  вершин.

Числа РамсеяПравить

 

Двухцветная раскраска $K_5$$K_{5}$  без одноцветных треугольников.

Минимальное число $R(r,s)$$R(r,\;s)$ , при котором это выполнено, называют числом Рамсея.

Например, равенство $R(3,3)=6$$R(3,\;3)=6$  означает, что с одной стороны в любой двухцветной раскраске полного графа $K_6$$K_{6}$  найдётся одноцветный треугольник, а с другой стороны — то, что полный граф $K_5$$K_{5}$  допускает двухцветную раскраску без одноцветных треугольников.

В общем случае для $c$$c$ -цветной раскраски используется обозначение $R(n_1,n_2,\dots <!--\; \dots \; -->,n_c)$$R(n_{1},\;n_{2},\;\ldots ,\;n_{c})$  для минимального числа вершин, обеспечивающего существование $K_{n_i}$$K_{n_{i}}$  для некоторого цвета $i$$i$ .

Доказательство теоремы РамсеяПравить

Двухцветный случайПравить

Лемма 1. $R(r,s)⩽<!--\; ⩽\; -->R(r-<!--\; -\; -->1,s)+R(r,s-<!--\; -\; -->1).$$R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1).$ 

Доказательство. Докажем с помощью метода математической индукции по $r+s$$r+s$ .

База индукции. $R(n,1)=R(1,n)=1$$R(n,\;1)=R(1,\;n)=1$ , так как 1-вершинный граф можно считать полным графом любого цвета.

Индукционный переход. Пусть $r>1$$r>1$  и $s>1$$s>1$ . Рассмотрим полный чёрно-белый граф из $R(r-<!--\; -\; -->1,s)+R(r,s-<!--\; -\; -->1)$$R(r-1,\;s)+R(r,\;s-1)$  вершин. Возьмём произвольную вершину $v$$v$  и обозначим через $M$$M$  и $N$$N$  множества инцидентные $v$$v$  в чёрном и белом подграфе соответственно. Так как в графе $R(r-<!--\; -\; -->1,s)+R(r,s-<!--\; -\; -->1)=|M|+|N|+1$$R(r-1,\;s)+R(r,\;s-1)=|M|+|N|+1$  вершин, согласно принципу Дирихле (комбинаторика), либо $|M|⩾<!--\; ⩾\; -->R(r-<!--\; -\; -->1,s)$$|M|\geqslant R(r-1,\;s)$ , либо $|N|⩾<!--\; ⩾\; -->R(r,s-<!--\; -\; -->1)$$|N|\geqslant R(r,\;s-1)$ .

Пусть $|M|⩾<!--\; ⩾\; -->R(r-<!--\; -\; -->1,s)$$|M|\geqslant R(r-1,\;s)$ . Тогда либо в $M$$M$  (и следовательно во всём графе) есть белый $K_s$$K_{s}$ , что завершает доказательство, либо в $M$$M$  есть чёрный $K_{r-<!--\; -\; -->1}$$K_{r-1}$ , который вместе с $v$$v$  образует чёрный $K_r$$K_{r}$ . Случай $|N|⩾<!--\; ⩾\; -->R(r,s-<!--\; -\; -->1)$$|N|\geqslant R(r,\;s-1)$  рассматривается аналогично.

Замечание. Если $R(r-<!--\; -\; -->1,s)$$R(r-1,\;s)$  и $R(r,s-<!--\; -\; -->1)$$R(r,\;s-1)$  оба чётны, неравенство можно усилить: $R(r,s)⩽<!--\; ⩽\; -->R(r-<!--\; -\; -->1,s)+R(r,s-<!--\; -\; -->1)-<!--\; -\; -->1$$R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)-1$ .

Доказательство. Предположим, $p=R(r-<!--\; -\; -->1,s)$$p=R(r-1,\;s)$  и $q=R(r,s-<!--\; -\; -->1)$$q=R(r,\;s-1)$  оба чётны. Положим $t=p+q-<!--\; -\; -->1$$t=p+q-1$  и рассмотрим чёрно-белый граф из $t$$t$  вершин. Если $d_i$$d_{i}$  степень $i$$i$ -й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, $\underset{i=1}{\overset{t}{\sum <!--\; \sum \; -->}}{d}_i$$\sum _{i=1}^{t}d_{i}$  — чётно. Поскольку $t$$t$  нечётно, должно существовать чётное $d_i$$d_{i}$ . Для определённости положим, что $d_1$$d_{1}$  чётно. Обозначим через $M$$M$  и $N$$N$  вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда $|M|=d_1$$|M|=d_{1}$  и $|N|=t-<!--\; -\; -->1-<!--\; -\; -->d_1$$|N|=t-1-d_{1}$  оба чётны. Согласно принципу Дирихле (комбинаторика), либо $|M|⩾<!--\; ⩾\; -->p-<!--\; -\; -->1$$|M|\geqslant p-1$ , либо $N⩾<!--\; ⩾\; -->q$$N\geqslant q$ . Так как $|M|$$|M|$  чётно, а $p-<!--\; -\; -->1$$p-1$  нечётно, первое неравенство можно усилить, так что либо $|M|⩾<!--\; ⩾\; -->p$$|M|\geqslant p$ , либо $|N|⩾<!--\; ⩾\; -->q$$|N|\geqslant q$ .

Предположим $|M|⩾<!--\; ⩾\; -->p=R(r-<!--\; -\; -->1,s)$$|M|\geqslant p=R(r-1,\;s)$ . Тогда либо подграф, порождённый множеством $M$$M$ , содержит белый $K_s$$K_{s}$  и доказательство завершено, либо он содержит чёрный $K_{r-<!--\; -\; -->1}$$K_{r-1}$ , который вместе с вершиной 1 образует чёрный $K_r$$K_{r}$ . Случай $|N|⩾<!--\; ⩾\; -->q=R(r,s-<!--\; -\; -->1)$$|N|\geqslant q=R(r,\;s-1)$  рассматривается аналогично.

Случай большего количества цветов.Править

Лемма 2. Если $c>2$$c>2$ , то $R(n_1,\dots <!--\; \dots \; -->,n_c)⩽<!--\; ⩽\; -->R(n_1,\dots <!--\; \dots \; -->,n_{c-<!--\; -\; -->2},R(n_{c-<!--\; -\; -->1},n_c)).$$R(n_{1},\;\ldots ,\;n_{c})\leqslant R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c})).$ 

Доказательство. Рассмотрим граф из $R(n_1,\dots <!--\; \dots \; -->,n_{c-<!--\; -\; -->2},R(n_{c-<!--\; -\; -->1},n_c))$$R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$  вершин и окрасим его рёбра $c$$c$  цветами. Будем временно считать цвета $c-<!--\; -\; -->1$$c-1$  и $c$$c$  одним цветом. Тогда граф становится $(c-<!--\; -\; -->1)$$(c-1)$ -цветным. Согласно определению числа $R(n_1,\dots <!--\; \dots \; -->,n_{c-<!--\; -\; -->2},R(n_{c-<!--\; -\; -->1},n_c))$$R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c}))$ , такой граф либо содержит $K_{n_i}$$K_{n_{i}}$  для некоторого цвета $i$$i$ , такого что $1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->c-<!--\; -\; -->2$$1\leqslant i\leqslant c-2$  либо $K_{R(n_{c-<!--\; -\; -->1},n_c)}$$K_{R(n_{c-1},\;n_{c})}$ , окрашенный общим цветом $c-<!--\; -\; -->1$$c-1$  и $c$$c$ . В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный $R(n_{c-<!--\; -\; -->1},n_c)$$R(n_{c-1},\;n_{c})$  — вершинный граф содержит либо $K_{n_{c-<!--\; -\; -->1}}$$K_{n_{c-1}}$  цвета $c-<!--\; -\; -->1$$c-1$ , либо $K_{n_c}$$K_{n_{c}}$  цвета $c$$c$ , так что утверждение полностью доказано.

Из леммы 1 следует конечность чисел Рамсея для $c=2$$c=2$ . Отсюда, на основании леммы 2, следует конечность $R(n_1,\dots <!--\; \dots \; -->,n_c)$$R(n_{1},\;\ldots ,\;n_{c})$  для любого $c$$c$ . Это доказывает теорему Рамсея.

Значения чисел РамсеяПравить

Таблица значенийПравить

Для $N(q_1,q_2,\dots <!--\; \dots \; -->,q_t;t)$$N(q_{1},\;q_{2},\;\ldots ,\;q_{t};\;t)$  при $t>2$$t>2$  имеется очень мало данных. Следующая таблица значений чисел Рамсея для $N(q_1,q_2;2)$$N(q_{1},\;q_{2};\;2)$  взята из таблицы Радзишевского^[en], данные приведены по состоянию на 2020 год.

$r,s$$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]	[59, 84]	[73, 115]	[92, 149]
5	1	5	14	25	[43, 48]	[58, 87]	[80, 143]	[101, 216]	[133, 316]	[149, 442]
6	1	6	18	[36, 41]	[58, 87]	[102, 165]	[115, 298]	[134, 495]	[183, 780]	[204, 1171]
7	1	7	23	[49, 61]	[80, 143]	[115, 298]	[205, 540]	[217, 1031]	[252, 1713]	[292, 2826]
8	1	8	28	[59, 84]	[101, 216]	[134, 495]	[217, 1031]	[282, 1870]	[329, 3583]	[343, 6090]
9	1	9	36	[73, 115]	[133, 316]	[183, 780]	[252, 1713]	[329, 3583]	[565, 6588]	[581, 12677]
10	1	10	[40, 42]	[92, 149]	[149, 442]	[204, 1171]	[292, 2826]	[343, 6090]	[581, 12677]	[798, 23556]

Асимптотические оценкиПравить

Из неравенства $R(r,s)⩽<!--\; ⩽\; -->R(r-<!--\; -\; -->1,s)+R(r,s-<!--\; -\; -->1)$$R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1)$  вытекает, что

$R(r,s)⩽<!--\; ⩽\; -->(\genfrac{}{}{0ex}{}{r+s-<!--\; -\; -->2}{r-<!--\; -\; -->1}).$$R(r,\;s)\leqslant {\binom {r+s-2}{r-1}}.$ 

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

$R(s,s)⩽<!--\; ⩽\; -->(1+o(1))\frac{4^{s-<!--\; -\; -->1}}{\sqrt{\mathrm{\pi <!--\; \pi \; -->}s}}.$$R(s,\;s)\leqslant (1+o(1)){\frac {4^{s-1}}{\sqrt {\pi s}}}.$ 

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

$R(s,s)⩾<!--\; ⩾\; -->(1+o(1))\frac{s}{\sqrt{2}e}{2}^{s/2},$$R(s,\;s)\geqslant (1+o(1)){\frac {s}{{\sqrt {2}}e}}2^{s/2},$ 

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

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

$(1+o(1))\frac{\sqrt{2}s}{e}{2}^{s/2}⩽<!--\; ⩽\; -->R(s,s)⩽<!--\; ⩽\; -->s^{-<!--\; -\; -->c\log <!--\; \; -->s/\log <!--\; \; -->\log <!--\; \; -->s}{4}^s.$$(1+o(1)){\frac {{\sqrt {2}}s}{e}}2^{s/2}\leqslant R(s,\;s)\leqslant s^{-c\log s/\log \log s}4^{s}.$ 

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

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

Известна также найденная Кимом в 1995 году оценка $R(3,t)⩾<!--\; ⩾\; -->\left(\frac{1}{162}+o(1)\right)\frac{t^2}{\ln <!--\; \; -->t}$$R(3,\;t)\geqslant \left({\frac {1}{162}}+o(1)\right){\frac {t^{2}}{\ln {t}}}$ . В сочетании с оценкой $R(3,t)⩽<!--\; ⩽\; -->(1+o(1))\frac{t^2}{\ln <!--\; \; -->t}$$R(3,\;t)\leqslant (1+o(1)){\frac {t^{2}}{\ln {t}}}$  это неравенство задаёт порядок роста величины $R(3,t)=\mathrm{\Theta <!--\; \Theta \; -->}\left(\frac{t^2}{\ln <!--\; \; -->t}\right)$$R(3,\;t)=\Theta \left({\frac {t^{2}}{\ln {t}}}\right)$ .

Вариации и обобщенияПравить

• Теорема Эрдёша — Радо — обобщениние теоремы Рамсея на несчётные множества.

• Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

СсылкиПравить

• Прасолов В. В. Теорема Рамсея (см. разбор задачи 22.7)
• Теория Рамсея

ЛитератураПравить

• Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.