Теорема Ремзі — теорема, винайдена англійським математиком Френком Ремзі, стосується комбінаторики, теорії графів та теорії множин.
Для двоколірного графа
Для довільних натуральних чисел існує натуральне число , таке що в повному графі з R(r, s) вершин, ребра якого розфарбовані в два кольори, знайдеться
- або повний розміру першого кольору,
- або повний підграф розміру другого кольору.
Теорема узагальнюється на довільну кількість кольорів та на гіперграфи.
Для гіперграфа
m-гіперграфом є гіперграф, ребра якого є набором із m вершин.
Для натуральних чисел , існує натуральне число таке, що повний m-гіперграф порядку R, ребра якого розфарбовані в c різних кольорів, в якому для деякого числа i від 1 до c, існує повний під-m-гіперграф порядку кольору i.
Теоретико-множинне формулювання
Якщо X зліченна множина і всі множини X(n) (підмножини X потужності n) розфарбовані в c різних кольорів. Тоді існує нескінченна підмножина M в X, така що всі підмножини M потужності n мають однаковий колір.
Див. також
Джерела
- Теорема Ремзі [ 22 грудня 2011 у Wayback Machine.]
- Теорія Ремзі [ 5 червня 2008 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет