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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Дво-кольоровий повний граф потужності 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 мають одинаковий колір.

Див. також[ред.ред. код]

Джерела[ред.ред. код]