Вероятностный метод в комбинаторике представляет собой мощный инструмент, позволяющий доказать существование определенных конфигураций в математических объектах путем введения случайности. В рамках лекции проекта MIT OpenCourseWare профессор Юфэй Чжао подробно разбирает один из самых ранних и классических примеров применения этого подхода — установление нижних границ для чисел Рамсея. Исторический экскурс охватывает ключевые вехи развития метода: от пионерской работы Пала Эрдёша до утонченного метода модификаций и применения локальной леммы Ловаса.
🧩 Что такое числа Рамсея и теорема Рамсея 0:00
Комбинаторика традиционно ищет порядок в хаосе, и числа Рамсея — один из ярких примеров такого поиска. Число Рамсея $R(k, l)$ определяется как наименьшее целое число $n$, при котором, как бы мы ни окрашивали ребра полного графа на $n$ вершинах (обозначаемого $K_n$) в два цвета (например, красный и зеленый), в нем обязательно найдется либо полный красный подграф (клика) на $k$ вершинах, либо полный зеленый подграф на $l$ вершинах. Полный граф означает, что между всеми $n$ вершинами проведены все возможные ребра, общее число которых составляет $\binom{n}{2}$.
Для лучшего понимания профессор приводит классический пример:
- Число Рамсея $R(3, 3) = 6$.
- Если взять граф с 6 вершинами и произвольно раскрасить все его ребра в красный или зеленый цвет, то математически неизбежно возникнет хотя бы один одноцветный треугольник — либо полностью красный, либо полностью зеленый.
- Однако если мы ограничимся лишь 5 вершинами, то существует способ раскрасить ребра так, чтобы полностью избежать появления монохроматических треугольников.
Фундаментальный результат, известный как теорема Рамсея, был доказан еще в 1920-х годах самим Фрэнком Рамсеем. Эта теорема постулирует, что число $R(k, l)$ всегда конечно для любых заданных параметров. Иными словами, если порядок графа достаточно велик, появление крупной одноцветной структуры становится гарантированным.
🎲 Вероятностный метод Пала Эрдёша: поиск «сена в стоге сена» 3:34
В 1940-х годах выдающийся математик Пал Эрдёш предложил принципиально новый способ нахождения нижних границ чисел Рамсея, который заложил основы вероятностного метода в дискретной математике. Эрдёш доказал, что для любого целого $k \ge 3$ диагональное число Рамсея удовлетворяет неравенству:
$$R(k, k) > 2^{k/2}$$
Это означает, что если граф имеет слишком мало вершин (меньше $2^{k/2}$), то всегда можно подобрать такую раскраску ребер, в которой не будет ни одной монохроматической клики размера $k$.
Юфэй Чжао предлагает доказать чуть более общее утверждение. Если два целых числа $n$ и $k$ удовлетворяют неравенству:
$$\binom{n}{k} 2^{1-\binom{k}{2}} < 1$$
то тогда $R(k, k) > n$.
Для доказательства применяется элегантная схема: ребра полного графа на $n$ вершинах окрашиваются абсолютно случайно. Мы подбрасываем симметричную монетку для каждого ребра: если выпадает орел — красим в красный, если решка — в зеленый. Чтобы доказать существование «хорошей» раскраски (без монохроматических $k$-клик), ученые вводят понятие «плохих событий» $A_s$ для каждого подмножества вершин $S$ размера $k$. Событие $A_s$ означает, что подграф на множестве $S$ оказался полностью одноцветным.
Вероятность такого нежелательного исхода для конкретного подмножества рассчитывается просто:
- Количество ребер в клике размера $k$ равно $\binom{k}{2}$.
- Вероятность того, что все они будут одного цвета (либо только красные, либо только зеленые), составляет $2 \cdot 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$.
Чтобы оценить вероятность того, что в графе возникнет хотя бы одна плохая клика, применяется неравенство Буля (union bound). Общая вероятность оценивается как сумма индивидуальных вероятностей по всем $\binom{n}{k}$ подмножествам:
$$\mathbb{P}(\text{существует плохая клика}) \le \binom{n}{k} 2^{1-\binom{k}{2}}$$
Поскольку по условию теоремы эта величина строго меньше 1, то с ненулевой (положительной) вероятностью случайная раскраска не будет содержать ни одной монохроматической клики размера $k$. Если вероятность существования такого объекта больше нуля, значит, он гарантированно существует. Из этого базового подхода путем асимптотических вычислений можно вывести более точную нижнюю границу:
$$R(k, k) > \frac{1 + o(1)}{e\sqrt{2}} k 2^{k/2}$$
где $e \approx 2.71$ — основание натурального логарифма.
Профессор Чжао обращает внимание на удивительный парадокс, который называют «поиском сена в стоге сена» (finding hay in a haystack). Если запустить этот алгоритм на компьютере, то случайная генерация выдаст нужный граф с огромной вероятностью, поскольку вероятность неудачи крайне мала. Однако проверить, что сгенерированный граф действительно не содержит плохих клик, невероятно трудно — для этого придется перебрать $\binom{n}{k}$ комбинаций, число которых растет экспоненциально. Поиск детерминированных способов конструирования таких графов до сих пор остается сложнейшей открытой задачей комбинаторики.
✂️ Метод модификаций: как улучшить оценку, исправив ошибки 14:49
Чтобы продвинуться дальше и получить более сильную оценку, математики разработали метод модификаций (alteration method). Его суть заключается в том, что мы сначала создаем случайный объект, а затем вручную устраняем в нем локальные дефекты.
Теорема метода модификаций утверждает, что для любых целых $k$ и $n$:
$$R(k, k) > n - \binom{n}{k} 2^{1-\binom{k}{2}}$$
Оптимизация параметра $n$ как функции от $k$ дает важное следствие — новую асимптотическую нижнюю границу:
$$R(k, k) > \frac{1 + o(1)}{e} k 2^{k/2}$$
Эта оценка улучшает результат простого вероятностного метода в $\sqrt{2}$ раз.
Алгоритм доказательства состоит из двух последовательных шагов:
- Мы берем полный граф на $n$ вершинах и красим каждое ребро случайно и независимо с равной вероятностью.
- В получившейся раскраске неизбежно возникнут «дефекты» — монохроматические клики размера $k$. На втором шаге мы просто удаляем по одной вершине из каждой такой клики, тем самым гарантированно разрушая их.
Для анализа этого процесса вводится случайная величина $X$, обозначающая количество монохроматических $k$-клик после первого шага. Ее математическое ожидание вычисляется аналогично предыдущему методу:
$$\mathbb{E}[X] = \binom{n}{k} 2^{1-\binom{k}{2}}$$
На втором шаге мы удаляем максимум $X$ вершин, поскольку некоторые удаленные вершины могут одновременно разрушить сразу несколько клик. Таким образом, в конечном графе останется как минимум $n - X$ вершин. Математическое ожидание числа оставшихся вершин будет равно $n - \mathbb{E}[X]$.
По законам теории вероятностей, если среднее значение величины равно некоторому числу, то с положительной вероятностью существует конкретный сценарий, где результат окажется не хуже среднего. Следовательно, существует граф, содержащий не менее этого количества вершин, в котором полностью отсутствуют монохроматические клики размера $k$.
⛓️ Зависимости событий и локальная лемма Ловаса 23:06
Предыдущие методы отлично работают, когда нам нужно избежать набора «плохих событий» $E_1, E_2, \dots, E_L$ в относительно простых условиях. Профессор выделяет две экстремальные ситуации, с которыми легко справляться математически:
- Когда в соответствии с неравенством Буля суммарная вероятность всех плохих событий мала.
- Когда все плохие события абсолютно независимы друг от друга. В этом случае вероятность того, что ни одно из них не произойдет, равна произведению вероятностей дополнений, и она гарантированно больше нуля, если индивидуальные вероятности строго меньше 1.
Однако в реальных и наиболее интересных задачах комбинаторики события почти всегда взаимосвязаны. Например, если две клики пересекаются по какому-то ребру, то их шансы стать монохроматическими зависимы. Для работы с такими «слабыми зависимостями» применяется мощнейший аппарат — локальная лемма Ловаса (Lovász Local Lemma).
Юфэй Чжао формулирует лемму в рамках модели независимых случайных величин. Пусть у нас есть набор независимых случайных величин $X_1, \dots, X_v$ (например, результаты бросков монеток для ребер графа). Каждому плохому событию $E_i$ (где $i$ меняется от 1 до $m$) соответствует свой индексный набор переменных $B_i$, от которых это событие зависит. Лемма выдвигает два ключевых условия:
- Каждое множество переменных $B_i$ пересекается (имеет общие переменные) не более чем с $d$ другими множествами $B_j$. Это жестко ограничивает степень зависимости событий.
- Вероятность каждого плохих событий ограничена сверху величиной $\frac{1}{e(d+1)}$.
Если оба условия выполнены, Ловас доказал, что вероятность того, что не произойдет ни одно из плохих событий $E_1, \dots, E_m$, строго больше нуля. Это дает зеленый свет для вывода еще более сильных математических оценок.
🏆 Теорема Спенсера: лучший результат из семидесятых 32:59
В 1970-х годах американский математик Джоэл Спенсер применил локальную лемму Ловаса к вычислению границ чисел Рамсея и совершил прорыв. Он доказал, что если параметры $n$ и $k$ удовлетворяют условию:
$$\left[ \binom{k}{2} \binom{n-2}{k-2} + 1 \right] 2^{1-\binom{k}{2}} < \frac{1}{e}$$
то число Рамсея $R(k, k)$ строго больше $n$.
Главная ценность этой теоремы раскрывается в ее асимптотическом следствии:
$$R(k, k) > \frac{\sqrt{2} + o(1)}{e} k 2^{k/2}$$
Этот результат превосходит оценку метода модификаций еще в $\sqrt{2}$ раз. На первый взгляд, выигрыш в константу кажется незначительным, однако данная планка, заданная Спенсером еще в прошлом веке, до сих пор остается лучшей известной нижней границей для диагональных чисел Рамсея.
Доказательство строится на аккуратном сопоставлении графовой задачи с моделью локальной леммы Ловаса. Мы снова случайным образом красим ребра графа $K_n$. Переменными модели выступают цвета каждого из $\binom{n}{2}$ ребер. Каждому подмножеству вершин $S$ размера $k$ соответствует плохое событие $E_s$ (клик на $S$ монохроматичен) с базовой вероятностью $2^{1-\binom{k}{2}}$. Множество ребер $B_s$ внутри клики имеет размер $\binom{k}{2}$.
Главная задача — посчитать параметр зависимости $d$, то есть сколько других клик $S'$ делят хотя бы одно общее ребро с кликой $S$. Две клики имеют общие ребра тогда и только тогда, когда они пересекаются как минимум по двум вершинам.
Расчет верхнего предела для $d$ выполняется следующим образом:
- Сначала мы выбираем пару вершин из нашей клики $S$, которая послужит зоной пересечения. Сделать это можно $\binom{k}{2}$ способами.
- Оставшиеся $k-2$ вершины для новой клики $S'$ мы добираем из оставшихся $n-2$ вершин графа, что дает $\binom{n-2}{k-2}$ вариантов.
Таким образом, количество пересекающихся клик не превышает произведения этих сочетаний. Подставив полученное значение $d$ в формулу локальной леммы Ловаса, мы убеждаемся, что условия теоремы полностью соблюдены. Из этого автоматически следует, что с положительной вероятностью ни одна из $k$-вершинных клик не окажется монохроматической. Существование такой раскраски доказано, а вместе с ним и историческая теорема Спенсера.
