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

---

Теорема Рамсея — теорема комбинаторики о разбиениях множеств, сформулированная и доказанная английским математиком Фрэнком Рамсеем в 1930 году^[1]. Встречается в литературе в разных формулировках. Эта теорема положила начало теории Рамсея.

Пусть ${\displaystyle p}$, ${\displaystyle q}$ и ${\displaystyle r}$ — натуральные числа, причём ${\displaystyle p,\;q\geqslant r}$.

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

---