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

Теорема Рамсея — теорема комбинаторики, открытая Франком Рамсеем, встречающаяся в литературе в нескольких формулировках:

Пусть $p$, $q$ и $r$ — натуральные числа, причем $p,\;q\geqslant r$. Тогда существует число $N=N(p,\;q,\;r)$, обладающее следующим свойством: если все $r$-элементные подмножества $N$-элементного множества $S$ произвольным образом разбиты на два непересекающихся семейства $\alpha$ и $\beta$, то либо существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся в $\alpha$, либо существует $q$-элементное подмножество, все $r$-элементные подмножества которого содержатся в $\beta$.

Для любых натуральных чисел N, K любой достаточно большой полный граф, ребра которого раскрашены в N цветов, содержит одноцветный полный подграф с K вершинами.

См. также

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

Ссылки

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

Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).