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

Теорема Рамсея — это совокупность утверждений комбинаторики, устанавливающих, что в любой достаточно большой структуре (графе, раскраске, множестве) обязательно найдётся однородная подструктура заданного размера. Теорема является основополагающим результатом теории Рамсея — раздела математики, изучающего условия возникновения порядка в хаотических системах. Названа в честь британского математика и философа Фрэнка Пламптона Рамсея, который в 1930 году опубликовал её первую версию в контексте логики и теории множеств.

История открытия

Предпосылки

В начале XX века математики активно исследовали основания математики и логики. Фрэнк Рамсей, работая над проблемой разрешимости для логики первого порядка, столкнулся с необходимостью доказать существование определённых комбинаторных конфигураций. В 1928 году он сформулировал и доказал утверждение, которое позже стало известно как «теорема Рамсея» (в узком смысле — для раскрасок рёбер графа).

Публикация и признание

Рамсей опубликовал свою работу «On a Problem of Formal Logic» (О проблеме формальной логики) в 1930 году, незадолго до своей смерти в возрасте 26 лет. Первоначально теорема не привлекла широкого внимания. В 1930-е годы её переоткрыл и популяризировал венгерский математик Пал Эрдёш, который вместе с Джорджем Секерешем развил теорию Рамсея в самостоятельную область комбинаторики. Эрдёш активно изучал числа Рамсея и сформулировал множество связанных задач, многие из которых остаются нерешёнными.

Развитие теории

Во второй половине XX века теория Рамсея расширилась за счёт включения бесконечных версий теоремы, многомерных обобщений и приложений в теории графов, информатике и теории множеств. В 1970-е годы были доказаны такие фундаментальные результаты, как теорема ван дер Вардена (об арифметических прогрессиях) и теорема Хейлса-Джюитта, которые также считаются частью теории Рамсея.

Формулировки теоремы

Классическая (конечная) версия для графов

Самая известная формулировка: для любых натуральных чисел \(r\) и \(s\) существует наименьшее целое число \(R(r,s)\), называемое числом Рамсея, такое, что любой полный граф с \(R(r,s)\) вершинами, рёбра которого раскрашены в два цвета (например, красный и синий), обязательно содержит либо красный полный подграф на \(r\) вершинах, либо синий полный подграф на \(s\) вершинах.

Пример: \(R(3,3) = 6\). Это означает, что на вечеринке из 6 человек обязательно найдутся либо трое попарно знакомых, либо трое попарно незнакомых. Для 5 человек это не гарантируется.

Бесконечная версия

Для бесконечных множеств: для любой раскраски рёбер полного графа на счётном множестве вершин в конечное число цветов существует бесконечное одноцветное подмножество вершин. Эта версия является прямым следствием леммы Кёнига и используется в теории множеств и топологии.

Многомерная версия (теорема Рамсея для гиперграфов)

Теорема обобщается на раскраску \(k\)-элементных подмножеств (\(k\)-гиперграфов). Для любых натуральных \(k, r, c\) существует число \(R_k(r; c)\) такое, что при раскраске всех \(k\)-элементных подмножеств множества размера \(R_k(r; c)\) в \(c\) цветов найдётся \(r\)-элементное подмножество, все \(k\)-элементные подмножества которого одноцветны.

Теорема ван дер Вардена (частный случай)

Является следствием теоремы Рамсея для арифметических прогрессий: при любой раскраске натуральных чисел в конечное число цветов существует одноцветная арифметическая прогрессия произвольной заданной длины.

Числа Рамсея

Определение и известные значения

Числа Рамсея \(R(r,s)\) для двух цветов — центральный объект исследования. Для малых значений они найдены:

Для \(R(5,5)\) точное значение не установлено, известны лишь нижняя (43) и верхняя (48) границы. Пал Эрдёш шутил, что если инопланетяне потребуют назвать \(R(5,5)\), человечество должно мобилизовать все компьютеры; если же потребуют \(R(6,6)\), лучше начать войну.

Асимптотические оценки

Для больших \(r\) и \(s\) точные значения неизвестны. Известна асимптотическая оценка: \[ R(k,k) \sim \frac{k \cdot 2^{k/2}}{e \sqrt{2}} \] (по Эрдёшу–Секерешу). Нижняя граница улучшена с помощью вероятностного метода.

Доказательство

Метод двойного счёта (для \(R(3,3)=6\))

1. Рассмотрим граф с 6 вершинами, рёбра раскрашены в два цвета.
2. Выберем произвольную вершину \(v\). У неё 5 инцидентных рёбер. По принципу Дирихле, хотя бы 3 из них одного цвета (например, красного).
3. Если среди трёх соседей \(v\) есть красное ребро, то вместе с \(v\) они образуют красный треугольник. Если нет — все рёбра между ними синие, и они образуют синий треугольник.
4. Для 5 вершин существует контрпример (цикл длины 5 с чередованием цветов), что доказывает минимальность числа 6.

Общий случай (индукция)

Доказательство конечной версии для произвольных \(r,s\) проводится двойной индукцией по \(r\) и \(s\) с использованием рекуррентного неравенства: \[ R(r,s) \le R(r-1,s) + R(r,s-1) \] Базовый случай: \(R(1,s)=1\), \(R(r,1)=1\). Индукционный шаг гарантирует существование числа для любых конечных \(r,s\).

Применения

В комбинаторике и теории графов

Теорема Рамсея используется для доказательства существования определённых подграфов в больших графах, например, в теории экстремальных графов (задача Турана). Она лежит в основе понятия «рамсеевского графа» — графа, не содержащего ни большого клика, ни большого независимого множества.

В информатике

В алгоритмической теории игр и сложности вычислений теорема Рамсея применяется для анализа алгоритмов на графах, в частности, для доказательства нижних оценок времени работы. Она также используется в теории баз данных (запросы на однородные подмножества) и в криптографии (конструкции псевдослучайных графов).

В логике и теории множеств

Бесконечная версия теоремы Рамсея является важным инструментом в дескриптивной теории множеств и теории моделей. Она применяется для доказательства теорем о компактности и полноте, а также в теории ультрафильтров.

В других областях

В социальных науках теорему Рамсея иногда используют для моделирования сетей знакомств и конфликтов (теория графов знакомств). В физике — для анализа фазовых переходов в случайных структурах.

Вариации и обобщения

Теорема Рамсея для бесконечных множеств (теорема Эрдёша–Радо)

Для любого кардинала \(\kappa\) и любого конечного числа цветов существует кардинал \(\lambda\) такой, что при раскраске рёбер полного графа на \(\lambda\) вершинах в \(c\) цветов найдётся одноцветный подграф мощности \(\kappa\).

Теорема Рамсея для частичных порядков

Для любого конечного частичного порядка существует такой большой частичный порядок, что при любой раскраске его элементов в конечное число цветов найдётся одноцветная копия исходного порядка (теорема Рамсея для порядков).

Теорема Хейлса-Джюитта

Обобщает теорему Рамсея на комбинаторные линии в многомерных кубах: для любых \(r\) и \(c\) существует \(N\) такое, что при раскраске всех точек \(r\)-мерного куба со стороной \(N\) в \(c\) цветов найдётся одноцветная комбинаторная линия длины \(r\).

Нерешённые проблемы

Точные значения чисел Рамсея

Для \(R(5,5)\) известен лишь диапазон (43–48). Для \(R(6,6)\) — 102–165. Для \(R(3,10)\) — 40–43. Вычисление точных значений требует колоссальных вычислительных ресурсов; для \(R(5,5)\) перебор всех графов на 43 вершинах невозможен (число графов порядка \(2^{903}\)).

Асимптотика для многомерных чисел

Для \(R_k(r; c)\) при \(k \ge 3\) известны лишь очень грубые оценки. Например, для \(R_3(4;2)\) (раскраска троек) точное значение неизвестно, нижняя граница — около 13, верхняя — около 23.

Связь с теорией случайных графов

Существует гипотеза, что для большинства чисел Рамсея случайные графы дают оптимальные нижние границы, но строгое доказательство отсутствует.

Интересные факты

• Фрэнк Рамсей опубликовал всего четыре математические работы, но его имя носит целая область комбинаторики.
• Пал Эрдёш называл теорию Рамсея «одной из самых красивых частей математики».
• Числа Рамсея растут экспоненциально: \(R(k,k)\) примерно равно \(2^{k/2}\), что делает их вычисление для \(k > 5\) практически невозможным.
• В 2018 году с помощью суперкомпьютера был найден точный граф для \(R(3,10) = 40\), что потребовало нескольких лет вычислений.

Источники

• Ф. П. Рамсей, «On a Problem of Formal Logic», 1930.
• П. Эрдёш, Дж. Секереш, «A combinatorial problem in geometry», 1935.
• Р. Грэм, Б. Ротшильд, Дж. Спенсер, «Теория Рамсея», 1990 (русский перевод: М.: Мир, 1991).
• В. Н. Сачков, «Комбинаторные методы дискретной математики», М.: Наука, 1977.
• Д. Кнут, «Искусство программирования», том 4А, раздел 7.2.2.