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