Теорема Рамсея: формулировка и пример для шести вершин

Теорема Рамсея утверждает: в достаточно большой структуре неизбежно найдётся упорядоченный фрагмент, даже если вся структура построена произвольно. Простейший пример относится к компании из шести человек: среди них обязательно найдутся трое попарно знакомых или трое попарно незнакомых. Предполагается, что знакомство взаимно и для каждой пары верна ровно одна из двух возможностей. Почему пяти человек ещё недостаточно? Интерактивный перебор ниже позволяет увидеть границу, а затем мы докажем её без компьютера.
От знакомства к раскраске рёбер
Заменим людей вершинами графа, а каждую пару соединим ребром. Получится полный граф: между любыми двумя различными вершинами проходит ровно одно ребро. Окрасим его в первый цвет, если люди знакомы, и во второй, если нет. Три попарно знакомых человека соответствуют треугольнику первого цвета; три попарно незнакомых - треугольнику второго.
В видео сначала показана раскраска пяти вершин без одноцветной тройки. Затем добавляется шестая вершина и её связи; золотым выделяется найденный треугольник. Это конкретный пример, а не проверка всех возможных вариантов добавления.
Графовая модель убирает детали, не влияющие на задачу: возраст людей, место встречи и причины знакомства. Важны только пары и их два возможных состояния. Похожий переход от условия к объектам и связям полезен в задачах о числах Шура, хотя там раскрашивают числа и ищут решение уравнения, а не треугольник сам по себе.
Формулировка и числа Рамсея
Для любых положительных целых и существует такое число , что при любой раскраске рёбер полного графа на вершинах в красный и синий найдётся либо красный полный подграф на вершинах, либо синий полный подграф на вершинах. Полный подграф называют также кликой: в нём присутствуют все рёбра между выбранными вершинами.
Наименьшее подходящее обозначают . Например, запись означает сразу два утверждения: шести вершин всегда достаточно, и пяти ещё может не хватить. Слова «при любой раскраске» существенны: один удачный рисунок на шести вершинах доказывает наличие треугольника лишь в этом рисунке.
Теорема распространяется и на любое фиксированное конечное число цветов, а также на более общие раскраски подмножеств. Здесь рассматривается конечный двухцветный случай для рёбер. Исходная работа Фрэнка Рамсея On a Problem of Formal Logic опубликована в 1930 году и связана с задачей математической логики.
Почему шести вершин достаточно
Выберем произвольную вершину . Из неё выходят пять рёбер к остальным вершинам. По принципу Дирихле хотя бы три из них одного цвета: иначе каждого цвета было бы не больше двух, всего не больше четырёх. Пусть для определённости эти три ребра красные, а их концы - , и .
Теперь рассмотрим три ребра между , и . Если хотя бы одно красное, скажем , то вместе с и оно образует красный треугольник. Если же ни одно из трёх рёбер не красное, все они синие, и вершины , , образуют синий треугольник. Случай, когда три ребра из синие, полностью симметричен.
Значит, любой двухцветный граф на шести вершинах содержит нужную тройку: . Аргумент не требует знать, как окрашены остальные рёбра. Он даёт и способ поиска: выбрать вершину, взять три соседних ребра одного цвета и проверить три ребра между их концами.
Почему пяти вершин недостаточно
Расположим пять вершин по кругу. Окрасим пять рёбер внешнего цикла в первый цвет, а пять оставшихся диагоналей - во второй. Рёбра каждого цвета образуют цикл длины пять. В цикле из пяти вершин нет треугольника: у каждой вершины есть лишь два соседа по циклу, и эти соседи не соединены ребром того же цикла.

Таким образом, показан контрпример для пяти вершин: . Вместе с верхней оценкой получаем точное равенство . Здесь нижняя и верхняя границы выполняют разные задачи: конкретная раскраска опровергает гарантию для пяти, а общий довод устанавливает гарантию для шести.
Что именно считает интерактив
Для помеченных вершин полный граф имеет рёбер. Каждое можно покрасить двумя способами, поэтому всего раскрасок . Для каждого варианта программа перебирает все тройки вершин и считает те, у которых три ребра одного цвета. Столбец над нулём показывает число раскрасок без таких троек.
При получается раскраски, из них 12 не содержат одноцветного треугольника. При программа проверяет раскрасок, и нулевой столбец пуст. Более того, в этом переборе минимум равен двум одноцветным треугольникам. Вершины и цвета считаются различимыми: поворот рисунка или обмен цветов может давать отдельную раскраску. Это подсчёт вариантов, а не вероятностное предсказание о реальной компании.
Перебор подтверждает результат в выбранном диапазоне, но с увеличением число вариантов растёт очень быстро. Для больших задач используют математические оценки, сокращение поиска по симметриям и проверяемые компьютерные доказательства. О том, насколько крупными могут оказаться оценки в родственной задаче, рассказывает статья про число Грэма.
Рекуррентная верхняя оценка
Для полезно неравенство
Обозначим сумму справа через и выберем вершину в произвольно раскрашенном полном графе на вершинах. Если у неё хотя бы красных соседей, то среди них есть красная клика размера , которую можно дополнить вершиной , либо синяя клика размера .
Иначе красных соседей не больше . Тогда из остальных соседей как минимум связаны с синими рёбрами. Среди них есть либо красная клика размера , либо синяя размера , которую дополняет . Оба случая дают требуемый результат. При базовых значениях это рассуждение также доказывает конечность чисел Рамсея индукцией.
Оценка не всегда точна: она гарантирует достаточное число вершин, но сама по себе не строит раскраску, показывающую необходимость именно такого числа. Различие между точным значением и верхней границей встречается и в других разделах математики; например, в статье о теореме Борсука - Улама рассматривается другая теорема о неизбежном совпадении, уже в топологии.
Как читать оценки на практике
Допустим, найдено число и раскраска графа на вершинах, в которой нет ни красной клики размера , ни синей размера . Тогда : до этого порога гарантия не работает. Если независимо доказано, что на вершинах нужная клика есть всегда, то . Пока , точное значение остаётся между границами; совпадение границ превращает оценку в точный ответ.
Важно сохранять порядок кванторов. Сначала фиксируют размеры искомых клик и число цветов, затем выбирают достаточное число вершин. Лишь после этого допускается любая раскраска. Число вершин в общем случае зависит от выбранных размеров, а теорема не обещает одной универсальной границы для всех размеров клик.
Где полезна идея
В информатике раскрашенный граф может кодировать два типа отношений между объектами. Теорема позволяет гарантировать однородную подсистему независимо от устройства всех остальных связей. Это полезно как инструмент доказательства существования, в частности в комбинаторике и теоретической информатике; она не утверждает, что найденная структура обязательно будет большой при любом практически заданном размере входа.
Числа Рамсея также связывают экстремальные конструкции с алгоритмами: для нижней границы ищут раскраску без запрещённой конфигурации, для верхней - доказывают, что следующую вершину добавить уже нельзя ни при каком выборе рёбер. В правиле суммы и произведения разобраны основы подсчёта, которые помогают определить число раскрасок для перебора.
Частые ошибки
- Считают, что все шесть человек должны быть знакомы друг с другом. Требуется только одна тройка с одинаковым отношением внутри неё.
- Забывают взаимность знакомства. Для направленного отношения нужна другая модель; обычное ребро описывает неупорядоченную пару.
- Доказывают равенство одним примером. Для нужны и раскраска на пяти вершинах, и доказательство для всех раскрасок на шести.
- Путают одноцветность с геометрическим положением. Пересечение нарисованных рёбер не создаёт новую вершину, если она явно не задана.
FAQ
Теорема указывает, какого цвета будет тройка?
Нет. Она гарантирует красную или синюю тройку, но конкретная раскраска определяет, какой случай встретится. Возможны и тройки обоих цветов.
Сколько рёбер и троек в графе на шести вершинах?
Рёбер , а наборов из трёх вершин . Одноцветными обязаны быть не все двадцать: достаточно одного, чтобы выполнить вывод теоремы.
Равно ли числу ?
Да. При обмене названий двух цветов условие меняется местами, поэтому вообще . Это симметрия определения, а не предположение о конкретной раскраске.
Коротко
Теорема Рамсея гарантирует одноцветную клику в достаточно большом полном графе с конечным числом цветов. В двухцветном случае : доказательство для шести вершин опирается на принцип Дирихле, а два пятиугольных цикла дают контрпример для пяти. Перебор помогает проверить малые случаи, но общая гарантия следует из доказательства.
Читайте также

Числа Шура: раскраски без монохромных троек
Числа Шура простыми словами: что такое S(r), теорема Шура о монохромных решениях x плюс y равно z, точные значения S(1)-S(5), связь с числами Рамсея и разбором задач.

Хроматический полином графа: как считать и применять
Что такое хроматический полином графа, как его вычислить через теорему об удалении и стягивании ребра, свойства коэффициентов и связь с хроматическим числом. Формулы и пошаговый пример.

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

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

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

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