Изменения

Перейти к: навигация, поиск

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

128 байт добавлено, 17:11, 30 ноября 2018
Числа Рамсея для раскрасок в несколько цветов
<tex dpi="150">2)r(k;n_1,\ldots,n_k) \le \dfrac{(n_1+n_2+\ldots+n_k)!}{n_1!\cdot n_2!\cdot \ldots\cdot n_k!}</tex>
|proof=
1) Доказательстве полностью аналогично пункту 1 доказательства [[#ter1|теоремы 1]] 2) Доказательство аналогично [[#u1|утверждению 1]]. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно Рассмотрим граф из чисел <tex>R(n_1,\;\ldots ,n_k\;n_{c-2},\;R(n_{c-1},\;n_c))</tex> вершин и окрасим его рёбра <tex>c</tex> равно цветами. Будем временно считать цвета <tex>c-1 </tex> и <tex>c</tex> одним цветом. Тогда граф становится <tex>(левая часть в этом случае равна 1, а правая, очевидно не меньше c-1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: </tex>-цветным. Согласно определению числа <tex dpi="150">\dfrac{R(n_1+n_2+ \ldots +n_k)!}{n_1!,\cdot n_2!\cdot ;\ldots ,\cdot n_k!;n_{c-2}=,\sum;R(n_{c-1},\limits_;n_c))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i = </tex>, такого что <tex>1}^k\dfracleqslant i\leqslant c-2</tex> либо <tex>K_{R(n_1+n_{c-1},\ldots+;n_c)}</tex>, окрашенный общим цветом <tex>c-1</tex> и <tex>c</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>R(n_in_{c-1)+ },\ldots +n_k;n_c)!</tex> — вершинный граф содержит либо <tex>K_{n_{c-1}}{n_1!\cdot \ldots \cdot (n_i</tex> цвета <tex>c-1)!\cdot \ldots \cdot n_k!</tex>, либо <tex>K_{n_c}</tex> Следовательноцвета <tex>c</tex>, 2 неравенство из данной [[#ter3|теоремы]] выводится из неравенства 1 по индукциитак что утверждение полностью доказано.
}}
442
правки

Навигация