Введение

Утверждение в математической комбинаторике

В комбинаторике теорема Рамзи, в одной из своих графовых формулировок, утверждает, что в любой раскраске ребер (в цвета) достаточно большого полного графа можно найти монохроматические клики. Чтобы проиллюстрировать теорему для двух цветов (например, синего и красного), пусть r и s – любые два положительных целых числа. Теорема Рамзи утверждает, что существует наименьшее положительное целое число R(r, s), для которого любая сине-красная раскраска ребер полного графа на R(r, s) вершинах содержит синюю клику на r вершинах или красную клику на s вершинах. (Здесь R(r, s) обозначает целое число, зависящее как от r, так и от s.)

Теорема Рамзи является основополагающим результатом в комбинаторике. Первая версия этого результата была доказана Фрэнком Рэмси. Это положило начало комбинаторной теории, теперь называемой теорией Рамзи, которая ищет закономерности в хаосе: общие условия существования подструктур с регулярными свойствами. В данном случае речь идет о существовании монохроматических подмножеств, то есть подмножеств связанных ребер только одного цвета. Обобщение этой теоремы применимо к любому конечному числу цветов, а не только к двум. Более точно, теорема утверждает, что для любого заданного числа цветов c и любых целых чисел существует число такое, что если ребра полного графа порядка окрашены в c различных цветов, то для некоторого i от 1 до c он должен содержать полный подграф порядка , все ребра которого окрашены в цвет i. Частный случай, рассмотренный выше, соответствует 1=c=2 (и и ).

R{3, 3) = 6

Предположим, что рёбра полного графа на 6 вершинах окрашены в красный и синий цвета. Выберем вершину, v. К вершине v инцидентно 5 рёбер, и поэтому (по принципу Дирихле) по крайней мере 3 из них должны быть одного цвета. Без потери общности можно предположить, что по крайней мере 3 из этих рёбер, соединяющих вершину v с вершинами r, s и t, синие. (Если нет, то в дальнейшем поменяйте красный и синий местами.) Если какое-либо из рёбер (rs), (rt), (st) также синее, то у нас есть полностью синий треугольник. Если нет, то эти три ребра все красные, и у нас есть полностью красный треугольник. Поскольку этот аргумент работает для любой раскраски, любой полный граф на 6 вершинах содержит монохроматический треугольник, и, следовательно, R(3, 3) ≤ 6. Популярная версия этого утверждения называется теоремой о друзьях и незнакомцах. Альтернативное доказательство использует двойной подсчёт. Оно выглядит следующим образом: посчитаем количество упорядоченных троек вершин x, y, z, таких что ребро (xy) красное, а ребро (yz) синее. Во-первых, для любой заданной вершины будет либо 0 = 0 × 5 = 0 (все рёбра от вершины одного цвета), либо 1 = 1 × 4 = 4 (четыре ребра одного цвета, одно другого цвета), либо 2 = 2 × 3 = 6 (три ребра одного цвета, два другого цвета) таких троек. Следовательно, существует не более 6 × 6 = 36 таких троек. Во-вторых, для любого немонохроматического треугольника (xyz) существует ровно две такие тройки. Следовательно, существует не более 18 немонохроматических треугольников. Поэтому, по крайней мере, 2 из 20 треугольников в полном графе монохроматичны. И наоборот, можно раскрасить полный граф на 6 вершин двумя цветами, не создавая ни одного монохроматического треугольника, показывая, что R(3, 3) > 5. Уникальная раскраска показана справа. Таким образом, R(3, 3) = 6. Задача доказать, что R(3, 3) ≤ 6 была одной из задач математического конкурса Уильяма Лоуэлла Путнама в 1953 году, а также в Венгерской математической олимпиаде в 1947 году.

Случай с несколькими цветами

Лемма 2. Если c > 2, то

Доказательство. Рассмотрим полный граф из вершин и окрасим его ребра в c цветов. Теперь "станем дальтониками" и представим, что c − 1 и c – это один и тот же цвет. Таким образом, граф теперь окрашен в (c − 1) цветов. По определению, такой граф содержит либо монохроматическое раскрашенное подграфом цветом i для некоторого 1 ≤ i ≤ c − 2, либо подграф, окрашенный в "смешанном цвете". В первом случае мы закончили. Во втором случае, мы снова восстанавливаем зрение и видим, что по определению, должен существовать либо (c − 1)-монохромный подграф, либо c-монохромный подграф. В обоих случаях доказательство завершено. Лемма 1 подразумевает, что любое R(r, s) конечно. Правая часть неравенства в Лемме 2 выражает число Рамзи для c цветов через числа Рамзи для меньшего числа цветов. Следовательно, любое R(r, s) конечно для любого числа цветов. Это доказывает теорему.

Числа Рамзи

Числа R(r, s) в теореме Рамзи (и их обобщения на более чем два цвета) известны как числа Рамзи. Число Рамзи R(m, n) дает решение задачи о вечеринке, которая спрашивает, какое минимальное количество гостей, R(m, n), необходимо пригласить, чтобы как минимум m человек знали друг друга или как минимум n человек не знали друг друга. На языке теории графов, число Рамзи – это минимальное число вершин, v = R(m, n), такое, что любой ненаправленный простой граф порядка v содержит клику порядка m или независимое множество порядка n. Теорема Рамзи утверждает, что такое число существует для всех m и n.

По симметрии верно, что R(m, n) = R(n, m). Верхнюю границу для R(r, s) можно получить из доказательства теоремы, а другие рассуждения дают нижние границы. (Первая экспоненциальная нижняя граница была получена Полом Эрдошем с использованием вероятностного метода.) Однако существует значительный разрыв между наиболее точными нижними и верхними границами. Также существует очень мало пар чисел r и s, для которых мы знаем точное значение R(r, s). Вычисление нижней границы L для R(r, s) обычно требует демонстрации раскраски графа в два цвета (синий/красный) без синего подграфа и без красного подграфа. Такой контрпример называется графом Рамзи. Брендан МакКей ведет список известных графов Рамзи. Установление верхних границ часто значительно сложнее: либо нужно проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо представить математическое доказательство его отсутствия.

Комплексность вычислений

Современной компьютерной программе не требуется рассматривать каждую раскраску по отдельности, чтобы исключить все возможные варианты; тем не менее, это очень сложная вычислительная задача, с которой существующее программное обеспечение справляется только для небольших размеров графов. Каждый полный граф имеет *n*( *n* - 1) / 2 ребер, поэтому при полном переборе необходимо будет просмотреть в общей сложности *c*^*(*n*( *n* - 1) / 2*) графов (для *c* цветов). Следовательно, вычислительная сложность поиска всех возможных графов полным перебором составляет O(*c*^*(*n*( *n* - 1) / 2*)), где *c* – количество цветов, а *n* – максимальное число узлов. Ситуация вряд ли изменится с появлением квантовых компьютеров. Один из наиболее известных алгоритмов поиска в неструктурированных данных демонстрирует лишь квадратичное ускорение (например, алгоритм Гровера) по сравнению с классическими компьютерами, поэтому время вычислений по-прежнему растет экспоненциально с увеличением числа узлов.

Индуцированный Рамзи

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

Заявление

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

Особые случаи

В то время как общие границы для индуцированных чисел Рамзи являются экспоненциальными относительно размера графа, поведение существенно отличается для специальных классов графов (в частности, разреженных). Для многих из этих классов индуцированные числа Рамзи являются полиномиальными по числу вершин. Если H — цикл, путь или звезда на k вершинах, то известно, что индуцированное число Рамзи линейно зависит от k. Также известно, что оно сверхлинейно (т.е. ). Следует отметить, что это контрастирует с обычными числами Рамзи, где гипотеза Бурра — Эрдёша (теперь доказанная) утверждает, что r(H) линейно зависит от k (поскольку деревья являются 1-вырожденными). Для графов H с числом вершин k и ограниченной степенью Δ было предположено, что , для некоторой константы d, зависящей только от Δ. Этот результат был впервые доказан Łuczak и Rödl в 1996 году, при этом d(Δ) росло как башня из двоек высотой. С тех пор были получены более разумные оценки для d(Δ). В 2013 году Конлон, Фокс и Чжао показали, используя лемму подсчёта для разреженных псевдослучайных графов, что , где показатель является наилучшим возможным с точностью до постоянных множителей.

Обобщения

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

Больше цветов

Мы также можем обобщить теорему Рамси на случай нескольких цветов. Для графов H, обозначим через r(H, r) минимальное число вершин в графе G, такое что любое раскрашивание рёбер G в r цветов содержит индуцированный подграф, изоморфный H, у которого все рёбра окрашены в i-й цвет для некоторого 1 ≤ i ≤ r. Пусть H(q) обозначает (q копий H). Можно вывести оценку для r(H(q), r), которая приблизительно представляет собой башню высоты ~ log q, итеративно применяя оценку для случая двух цветов. Наилучшая на данный момент известная оценка принадлежит Фоксу и Судакову и достигает O(k^(c log q)), где k – число вершин H, а c – константа, зависящая только от q.

Гиперграфы

Мы можем расширить определение индуцированных чисел Рамзи на d-однородные гиперграфы, просто заменив слово «граф» в формулировке на «гиперграф». Кроме того, многоцветную версию индуцированных чисел Рамзи можно определить тем же способом, что и в предыдущем подразделе. Пусть H — d-однородный гиперграф с k вершинами. Определим функцию башню, положив и для i ≥ 1, . Используя метод контейнеров для гиперграфов, Конлон, Деламоника, Ла Флер, Рёдль и Шахт показали, что для d ≥ 3, q ≥ 2, для некоторой константы c, зависящей только от d и q. В частности, этот результат соответствует наилучшей известной оценке для обычного числа Рамзи при d = 3.

Бесконечные графики

Дальнейший результат, также известный как теорема Рамзи, применим к бесконечным графам. В контексте, где также обсуждаются конечные графы, его часто называют «теоремой бесконечного Рамзи». Поскольку интуиция, предоставляемая наглядным представлением графа, ослабевает при переходе от конечных к бесконечным графам, теоремы в этой области обычно формулируются на языке теории множеств. Теорема. Пусть X — некоторое бесконечное множество, и раскрасим элементы (подмножества X размера n) в c различных цветов. Тогда существует бесконечное подмножество M множества X, такое что все подмножества размера n из M имеют один и тот же цвет. Доказательство: Доказательство проводится индукцией по n, размеру подмножеств. Для n = 1 утверждение эквивалентно тому, что если бесконечное множество разделить на конечное число множеств, то одно из них будет бесконечным. Это очевидно. Предположим, что теорема верна для n ≤ r, и докажем ее для n = r + 1. Пусть задано c-раскрашивание (r + 1)-элементных подмножеств X. Возьмем элемент x из X и обозначим Y = X \ {x}. Затем индуцируем c-раскрашивание r-элементных подмножеств Y, просто добавляя x к каждому r-элементному подмножеству (получая таким образом (r + 1)-элементное подмножество X). По предположению индукции, существует бесконечное подмножество Z множества Y, такое что каждое r-элементное подмножество Z имеет один и тот же цвет в индуцированном раскрашивании. Таким образом, существует элемент y из Z и бесконечное подмножество W множества Z, такие что все (r + 1)-элементные подмножества X, состоящие из y и r элементов из W, имеют один и тот же цвет. По аналогичному аргументу, существует элемент z из W и бесконечное подмножество V множества W с теми же свойствами. Индуктивно мы получаем последовательность {x_i}, такую что цвет каждого (r + 1)-элементного подмножества {x_{i_1}, x_{i_2}, ..., x_{i_{r+1}}} с i_1 < i_2 < ... < i_{r+1} зависит только от значения i_1. Более того, существует бесконечно много значений i_n, для которых этот цвет будет одинаковым. Выберем эти x_{i_n}, чтобы получить требуемое монохромное множество. Более сильная, но несбалансированная бесконечная форма теоремы Рамзи для графов, теорема Эрдеша — Душника — Миллера, утверждает, что каждый бесконечный граф содержит либо счетное бесконечное независимое множество, либо бесконечную клику той же кардинальности, что и исходный граф.

Гиперграфы

Теорема также может быть расширена на гиперграфы. Гиперграф m – это граф, "рёбра" которого представляют собой множества из m вершин – в обычном графе ребро является множеством из 2 вершин. Полная формулировка теоремы Рамзи для гиперграфов заключается в том, что для любых целых чисел m и c, и любых целых чисел , существует такое целое число , что если гиперрёбра полного m-мерного гиперграфа порядка окрашены в c различных цветов, то для некоторого i между 1 и c гиперграф должен содержать полный подгиперграф порядка m, все гиперрёбра которого имеют цвет i. Эта теорема обычно доказывается индукцией по m, "многомерности" графа. Базовый случай для доказательства – m=2, что является точно теоремой, сформулированной выше. Для m=3 мы знаем точное значение одного нетривиального числа Рамзи, а именно R(4, 4; 3) = 13. Этот факт был установлен Бренданом Маккеем и Станиславом Радзишевским в 1991 году. Кроме того, у нас есть: R(4, 5; 3) ≥ 35, R(4, 6; 3) ≥ 63 и R(5, 5; 3) ≥ 88.

Бесчисленные кардиналы

В терминах исчисления разбиений теорему Рамзи можно сформулировать как для всех конечных n и k. Вацлав Серпинский показал, что теорема Рамзи не обобщается на графы размера, продемонстрировав, что В частности, гипотеза континуума влечет, что Стево Тодорчевич показал, что на самом деле в ZFC, , что является гораздо более сильным утверждением, чем Джастин Т. Мур, который еще больше усилил этот результат. Что касается положительных результатов, кардинал Рамзи, , — это большой кардинал, аксиоматически определяемый для удовлетворения соответствующей формулы: Существование кардиналов Рамзи нельзя доказать в ZFC.

Отношение к аксиоме выбора

В обратной математике существует существенная разница в силе доказательств между версией теоремы Рамзи для бесконечных графов (случай n = 2) и для бесконечных мультиграфов (случай n ≥ 3). Мультиграфная версия теоремы эквивалентна по силе аксиоме арифметического понимания, что включает её в подсистему ACA0 арифметики второго порядка – одну из пяти основных подсистем в обратной математике. В отличие от этого, по теореме Дэвида Ситапуна, версия теоремы для графов слабее ACA0, и (в сочетании с другими результатами Ситапуна) не входит ни в одну из пяти основных подсистем. Однако над ZF версия для графов влечет классическую лемму Кёнига, в то время как обратное неверно, поскольку в этом контексте лемма Кёнига эквивалентна аксиоме счётного выбора из конечных множеств.