- Теорема Рамсея
-
Теорема Рамсея — теорема комбинаторики, открытая Франком Рамсеем, встречающаяся в литературе в нескольких формулировках:
Пусть , и — натуральные числа, причем . Тогда существует число , обладающее следующим свойством: если все -элементные подмножества -элементного множества произвольным образом разбиты на два непересекающихся семейства и , то либо существует -элементное подмножество множества , все -элементные подмножества которого содержатся в , либо существует -элементное подмножество, все -элементные подмножества которого содержатся в .
Для любых натуральных чисел N, K любой достаточно большой полный граф, ребра которого раскрашены в N цветов, содержит одноцветный полный подграф с K вершинами.
См. также
Ссылки
Для улучшения этой статьи желательно?: - Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
Категории:- Комбинаторика
- Теоремы
- Теория множеств
Wikimedia Foundation. 2010.