Теорема Рамсея и числа Рамсея

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

Definition

Число Рамсея R(s,t) — это наименьшее целое число n, такое что любая красно-синяя раскраска рёбер полного графа с n вершинами содержит красную клику из s вершин или синюю клику из t вершин.

Scope

Эта тема охватывает графовую форму теоремы Рамсея, определение чисел Рамсея R(s,t), классические малые случаи, такие как R(3,3)=6, верхнюю границу Эрдеша-Секереша и вероятностную нижнюю границу Эрдеша, а также расширение на многоцветные и гиперграфовые числа Рамсея. Это количественное ядро теории Рамсея.

Core questions

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

Key concepts

• Теорема Рамсея для графов
• Число Рамсея R(s,t)
• Монохроматические клики
• Граница Эрдеша-Секереша
• Вероятностные нижние границы
• Многоцветные и гиперграфовые числа Рамсея

Key theories

Верхняя граница Эрдеша-Секереша

Числа Рамсея конечны и ограничены R(s,t), которое не превышает биномиального коэффициента из s+t-2 по s-1; это рекуррентная граница, которая доказывает теорему Рамсея с явными оценками.

Вероятностная нижняя граница Эрдеша

Подсчитывая ожидаемые монохроматические клики в случайной раскраске, Эрдеш в 1947 году показал, что диагональное число Рамсея R(s,s) растет как минимум экспоненциально, что стало одним из основополагающих применений вероятностного метода.

Clinical relevance

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

History

Эрдеш и Секереш заново открыли и количественно определили теорему Рамсея в 1935 году, изучая выпуклые многоугольники; нижняя граница случайной раскраски Эрдеша 1947 года положила начало вероятностному методу.

Key figures

• Frank Ramsey
• Paul Erdos
• George Szekeres

Seminal works

• graham1990

Frequently asked questions

Почему R(3,3) равно шести?

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

Известны ли точные числа Рамсея?

Точно известно лишь небольшое количество; даже R(5,5) остается открытым, при этом текущие знания лишь сужают его до определенного диапазона, поскольку пространство поиска растет слишком быстро, чтобы решить задачу вычислениями.