442
правки
Изменения
→Числа Рамсея для раскрасок в несколько цветов
Отметим, что <tex>r(2;n,m)</tex> — это определённое ранее число Рамсея <tex>r(n,m)</tex>
{{Теорема
|id=ter3|about=3
|statement=<tex>\forall k, n_1, \ldots n_k, \in \mathbb N </tex>Если существует соответственное число Рамсея <mathtex>c>2r(k;n_1,\ldots,n_k)</mathtex>, то при этом <mathtex>Rr(k, n_1,\;\ldots,\;n_cn_k)\leqslant Rr(k-1, n_1,\;\ldots,\;n_{ck-2},\;Rr(n_{ck-1},\;n_cn_k)).</mathtex>
|proof=
Рассмотрим граф из <tex>Rr(k-1, n_1,\;\ldots,\;n_{ck-2},\;Rr(n_{ck-1},\;n_cn_k))</tex> вершин и окрасим его рёбра <tex>ck</tex> цветами. Будем временно считать цвета <tex>ck-1</tex> и <tex>ck</tex> одним цветом. Тогда граф становится <tex>(ck-1)</tex>-цветным. Согласно определению числа <tex>Rr(k-1, n_1,\;\ldots,\;n_{ck-2},\;Rr(n_{ck-1},\;n_cn_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant ck-2</tex> либо <tex>K_{Rr(k, n_{ck-1},\;n_cn_k)}</tex>, окрашенный общим цветом <tex>ck-1</tex> и <tex>ck</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>Rr(n_{ck-1},\;n_cn_k)</tex> — вершинный граф содержит либо <tex>K_{n_{ck-1}}</tex> цвета <tex>ck-1</tex>, либо <tex>K_{n_cn_k}</tex> цвета <tex>ck</tex>, так что утверждение полностью доказано.
}}
