299
правок
Изменения
→Числа Рамсея для раскрасок в несколько цветов
===Числа Рамсея для раскрасок в несколько цветов===
{{Определение
|id=def2
|definition=
Пусть <tex>k,n_1,...,n_k \in \mathbb N</tex>. Число Рамсея <tex>r(k;n_1,...,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>.
}}
{{Утверждение
|id=u3
|statement=
Отметим, что <tex>r(2;n,m)</tex> — это определённое ранее число Рамсея <tex>r(n,m)</tex>
}}
Обобщение оказывается настолько естественным что по сути не добавляет нам ничего нового: полностью аналогично [[#t1|теореме]] и [[#ts1|следствию]] можно доказать следующие факты.
Тесрема Ю.З. Пусть k,ni,... ,пк > 2 — натуральные числа. Тогда выполняются слесукьиье утвержееьья.
1)
г (к; Hi,..., пк) < г (к; щ - 1, те2,... пк) + г (к; теь те2 - 1,... пк)+
+r(k;ni,n2,.. .пк — 1) - к+ 2. (ЮЗ)
2)
г{к;п1,...,пк)<—j : г. (10 1
пр. • те2! пк\
Доказательство. 1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 1С.]
2) Доказательство аналогично следстьик 1С.1 Нужно лишь убедиться в с невидном неравенстве для случая, когда хотя бы одне из чисел п\,...,пк равно ] (леьая часть в этом случае равна 1. а правая, оче-ьидно не меньше 1] и заметить, что полиьомиалъьыс кеэффиььенты из с невидных комбинаторных соображений удевл створяют соотношению
(те! + те2 + . ..пк)\ _ А (теН h (те, - 1) Н РтеД!
ni! • тг2! пк\ ^ теф (щ - 1)! пк\ '
2=1
Следовательно, неравенстьс (10.4) выводится из неравенства (1 С.З) по индукнии.
==Числа Рамсея больших размерностей==
