442
правки
Изменения
→Числа Рамсея для раскрасок в несколько цветов
{{Теорема
|id=ter3|about=3
|statement=Пусть <tex>\forall k,n_1,\ldotsn_k,n_k \ge in \mathbb N </tex>Если <math>c>2</texmath> {{---}} натуральные числа. Тогда выполняются следующие утверждения:, то <texmath>1) rR(k;n_1,\;\ldots,n_k\;n_c) \le rleqslant R(k;n_1-1,n_2,\ldots,n_k)+r(k;n_1,n_2-1,\ldots,n_k)+ \ldots +r(k;n_1,n_2n_{c-2},\ldots,n_k;R(n_{c-1)-k+2</tex><tex dpi="150">2)r(k;n_1},\ldots,n_k;n_c) \le \dfrac{(n_1+n_2+\ldots+n_k)!}{n_1!\cdot n_2!\cdot \ldots\cdot n_k!}.</texmath>
|proof=
Рассмотрим граф из <tex>R(n_1,\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_c))</tex> вершин и окрасим его рёбра <tex>c</tex> цветами. Будем временно считать цвета <tex>c-1</tex> и <tex>c</tex> одним цветом. Тогда граф становится <tex>(c-1)</tex>-цветным. Согласно определению числа <tex>R(n_1,\;\ldots,\;n_{c-2},\;R(n_{c-1},\;n_c))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant c-2</tex> либо <tex>K_{R(n_{c-1},\;n_c)}</tex>, окрашенный общим цветом <tex>c-1</tex> и <tex>c</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>R(n_{c-1},\;n_c)</tex> — вершинный граф содержит либо <tex>K_{n_{c-1}}</tex> цвета <tex>c-1</tex>, либо <tex>K_{n_c}</tex> цвета <tex>c</tex>, так что утверждение полностью доказано.
