Теорема Ремзі

Теорема Ремзі — теорема, винайдена англійським математиком Френком Ремзі, стосується комбінаторики, теорії графів та теорії множин.

Двоколірний повний граф потужності 5, без монохроматичного повного підграфа потужності 3

Для двоколірного графа

Для довільних натуральних чисел $\ r,s$ існує натуральне число $\ R(r,s)$, таке що в повному графі з R(r, s) вершин, ребра якого розфарбовані в два кольори, знайдеться

• або повний підграф розміру $\ r$ першого кольору,
• або повний підграф розміру $\ s$ другого кольору.

Теорема узагальнюється на довільну кількість кольорів та на гіперграфи.

Для гіперграфа

m-гіперграфом є гіперграф, ребра якого є набором із m вершин.

Для натуральних чисел $\ m,c,n_{1},\ldots ,n_{c}$, існує натуральне число $\ R(n_{1},\ldots ,n_{c};m)$ таке, що повний m-гіперграф порядку R, ребра якого розфарбовані в c різних кольорів, в якому для деякого числа i від 1 до c, існує повний під-m-гіперграф порядку $\ n_{i}$ кольору i.

Теоретико-множинне формулювання

Якщо X зліченна множина і всі множини X(n) (підмножини X потужності n) розфарбовані в c різних кольорів. Тоді існує нескінченна підмножина M в X, така що всі підмножини M потужності n мають однаковий колір.

Див. також

• Теорема Ердеша — Секереша
• Проблема трійок Буля — Піфагора

Джерела

• Теорема Ремзі [Архівовано 22 грудня 2011 у Wayback Machine.]
• Теорія Ремзі [Архівовано 5 червня 2008 у Wayback Machine.]