Оглавление
- 1 Теорема Рамсея
- 1.1 Теорема Рэмси
- 1.2 Расширение на несколько цветов
- 1.3 Примеры
- 1.4 Доказательство для двух цветов
- 1.5 Доказательство для нескольких цветов
- 1.6 Числа Рамсея
- 1.7 Определение числа Рамсея
- 1.8 Вычислительная сложность
- 1.9 Известные значения
- 1.10 Асимптотика
- 1.11 Формальная проверка чисел Рамсея
- 1.12 Индуцированный Рэмси
- 1.13 Определение и история
- 1.14 Верхние границы
- 1.15 Нижние границы
- 1.16 Обобщения
- 1.17 Бесконечные графы
- 1.18 Теорема Рамсея для гиперграфов
- 1.19 Числа Рамсея для ориентированных графов
- 1.20 Бесчисленные кардиналы
- 1.21 Связь с аксиомой выбора
- 1.22 Дополнительные ресурсы
- 1.23 Полный текст статьи:
- 2 Теорема Рамсея
Теорема Рамсея
-
Теорема Рэмси
- Теорема утверждает, что в любом полном графе с достаточно большим числом вершин можно найти монохроматические клики.
- Для двух цветов (синего и красного) существует наименьшее число R(r, s), для которого каждая раскраска содержит синюю клику в r вершинах или красную клику в s вершинах.
-
Расширение на несколько цветов
- Теорема применима к любому конечному числу цветов c и целых чисел n1, …, nc.
- Для c цветов и n1, …, nc существует число R(n1, …, nc), такое что если ребра графа раскрашены c цветами, то для некоторого i между 1 и c граф содержит полный подграф порядка ni, все ребра которого окрашены в i цвет.
-
Примеры
- R(3, 3) = 6: любой K6 содержит монохроматический K3.
- R(3, 3, 3) = 17: на K16 есть две раскраски, избегающие монохроматических треугольников.
-
Доказательство для двух цветов
- Теорема доказывается методом индукции по r + s.
- Для четных R(r – 1, s) и R(r, s – 1) неравенство индукции может быть усилено.
-
Доказательство для нескольких цветов
- Лемма 2: R(n1, …, nc) ≤ R(n1, …, nc – 2, R(nc – 1, nc)).
- Доказательство: график с R(n1, …, nc – 2, R(nc – 1, nc)) вершинами и c цветами содержит либо Kni, монохроматически окрашенный цветом i, либо KR(nc – 1, nc).
-
Числа Рамсея
- Числа R(r, s) известны как числа Рамсея.
- R(m, n) дает решение задачи о вечеринке, где задается минимальное количество гостей, которые должны быть приглашены, чтобы по крайней мере m знали друг друга или по крайней мере n не знали друг друга.
-
Определение числа Рамсея
- Число Рамсея R(m, n) — минимальное число вершин, такое, что все неориентированные простые графы порядка v содержат клику порядка m или независимое множество порядка n.
- Теорема Рэмси утверждает, что такое число существует для всех m и n.
- R(m, n) = R(n, m) из-за симметрии.
-
Вычислительная сложность
- Вычисление нижней границы L для R(r, s) требует отображения сине-красной окраски графа KL-1 без синего подграфа Kr и красного подграфа Ks.
- Верхние границы часто сложнее установить, требуется либо проверка всех возможных вариантов раскраски, либо математический аргумент.
- Вычислительная сложность поиска по всем возможным графам составляет O(cn2) для c раскрасок и не более n узлов.
-
Известные значения
- R(3, 3) = 6, R(4, 2) = 4, R(s, 2) = s для всех s.
- R(4, 3) ≤ R(4, 2) + R(3, 3) − 1 = 9, R(4, 4) ≤ R(4, 3) + R(3, 4) ≤ 18.
- R(4, 5) = 25, R(5, 5) неизвестно, но находится между 43 и 46.
- R(r, s) при r, s ≤ 10 приведены в таблице.
-
Асимптотика
- Неравенство R(r, s) ≤ R(r − 1, s) + R(r, s − 1) доказано Эрдешем и Секересом.
- Экспоненциальная нижняя граница дана Эрдешем в 1947 году.
- Для диагональных чисел Рамсея известны нижние и верхние границы, улучшенные в 2023 году.
- Для недиагональных чисел Рамсея R(3, t) известны верхние и нижние границы, улучшенные в 2023 году.
-
Формальная проверка чисел Рамсея
- R(3, 8) = 28 подтверждено с использованием методов логической выполнимости и систем компьютерной алгебры.
- R(4, 5) = 25 подтверждено с использованием интерактивного средства проверки теорем HOL4.
-
Индуцированный Рэмси
- Существует аналог теоремы Рэмси для индуцированных подграфов.
- Индуцированное число Рамсея rind(H) — наименьшее число вершин графа G, содержащего монохроматическую индуцированную копию H.
-
Определение и история
- rind(X, Y) — наименьшее число вершин графа G, где каждая раскраска ребер содержит красный или синий индуцированный подграф X или Y.
- В начале 1970-х Эрдеш, Хайнал и Пуса доказали существование индуцированных чисел Рамсея.
- Эрдеш предположил, что rind(H) ≤ 2ck, но это остается открытой гипотезой.
-
Верхние границы
- В 1998 году Кохаякава, Перемель и Редль доказали rind(H) ≤ 2ck(log k)2.
- В 2008 году Фокс и Судаков улучшили оценку до rind(H) ≤ 2ck log k.
- В 2010 году Конлон, Фокс и Судаков показали, что rind(H) ≤ 2ck log k, что остается наилучшей верхней границей.
-
Нижние границы
- Для циклов, траекторий и звезд rind(H) линейна по k.
- Для деревьев rind(H) = O(k2 log2k).
- Для графов с ограниченной степенью Δ rind(H) ≤ cnd(Δ).
-
Обобщения
- Индуцированные числа Рамсея можно обобщить на гиперграфы и многоцветные настройки.
- Для гиперграфов rind(H;q) ≤ td(ck) для d ≥ 3 и q ≥ 2.
-
Бесконечные графы
- Теорема Рэмси применима к бесконечным графам.
- Доказательство проводится индукцией по размеру подмножеств.
- Бесконечная версия теоремы подразумевает конечную версию.
-
Теорема Рамсея для гиперграфов
- Для любых целых чисел m и c и n1, …, nc существует число R(n1, …, nc; m), такое что если гиперграницы полного m-гиперграфа окрашены в c цветов, то существует полный под-m-гиперграф с гиперграницами, окрашенными в i цвет.
- Теорема доказывается индукцией по m.
- Для m = 3 известно точное значение R(4, 4; 3) = 13.
-
Числа Рамсея для ориентированных графов
- Введены П. Эрдешем и Л. Мозером в 1964 году.
- R(n) – наименьшее число Q, такое что полный граф с ≥ Q узлами содержит ациклический n-узловой подграф.
- R(0) = 0, R(1) = 1, R(2) = 2, R(3) = 4, R(4) = 8, R(5) = 14, R(6) = 28, 34 ≤ R(7) ≤ 47.
-
Бесчисленные кардиналы
- Теорема Рамсея может быть сформулирована в терминах разбиений.
- Вацлав Серпиньский показал, что теорема не распространяется на графики размера ℵ1.
- Стево Тодорчевич и Джастин Т. Мур укрепили этот результат.
- Кардинал Рэмси κ удовлетворяет формуле κ → (κ)2<ω.
-
Связь с аксиомой выбора
- В обратной математике существует разница в силе доказательства между версиями теоремы для бесконечных графов и мультиграфов.
- Многографическая версия эквивалентна аксиоме арифметического понимания.
- Графическая версия слабее, чем ACA0, и не попадает в подсистемы “большой пятерки”.
- В ZF графическая версия подразумевает лемму Кенига, но обратное следствие не выполняется.
-
Дополнительные ресурсы
- Ramsey@Home – проект распределенных вычислений для поиска нижних границ чисел Рамсея.
- Электронный журнал комбинаторики “Динамический обзор малых чисел Рамсея”.
- Число Рамсея из MathWorld содержит нижние и верхние границы до R(19, 19).
- Число Рэмси – Джеффри Эксоо содержит контрдоказательства для R(5, 5) > 42.