Вероятностный метод в комбинаторике

Идея вероятностного существования и нижние оценки чисел Рамсея

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

Этот подход получил название вероятностного метода. Его суть парадоксальна: чтобы доказать существование детерминированного объекта с заданным свойством, мы погружаем всё множество объектов в вероятностное пространство. Если вероятность того, что случайно выбранный объект обладает нужным свойством, строго больше нуля, то такой объект обязан существовать.

Числа Рамсея и проблема явной конструкции

Классическая теорема Рамсея утверждает: для любого натурального числа $k \ge 3$ существует такое минимальное число $N$, что при произвольной раскраске рёбер полного графа $K_N$ в два цвета (например, красный и синий) обязательно найдётся монохроматический полный подграф $K_k$ — клика размера $k$, все рёбра которой окрашены в один цвет. Это минимальное $N$ обозначается как $R(k, k)$ (диагональное число Рамсея).

Известная шуточная интерпретация для $k = 3$: в любой группе из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых ($R(3, 3) = 6$). Верхнюю оценку для произвольного $k$ ещё в 1935 году получили Дьёрдь Секереш и Пал Эрдёш с помощью простого индуктивного шага:

$$R(k, k) \le \binom{2k - 2}{k - 1} < 4^k$$

Здесь $\binom{2k - 2}{k - 1}$ — биномиальный коэффициент («число сочетаний из $2k-2$ по $k-1$»), задающий число способов выбрать $k-1$ элемент из $2k-2$. При больших $k$ по формуле Стирлинга эта величина растёт как $\frac{4^{k-1}}{\sqrt{\pi k}}$, то есть не превосходит геометрической прогрессии со знаменателем 4.

Но какова нижняя граница? Чтобы доказать неравенство $R(k, k) > n$, необходимо предъявить контрпример: хотя бы одну раскраску рёбер графа $K_n$ в два цвета, в которой нет ни одного одноцветного подграфа $K_k$.

Допустим, мы хотим доказать это прямым перебором или явной симметричной конструкцией. На графе с $n$ вершинами всего существует:

$$\binom{n}{2} = \frac{n(n - 1)}{2}$$

рёбер, а значит, общее число различных 2-раскрасок равно $2^{\binom{n}{2}}$. Уже для скромного значения $n = 40$ число вариантов превышает $10^{230}$, что на порядки больше числа атомов в наблюдаемой Вселенной. Явные алгебраические построения (например, графы Пэли или вычеты по модулю) давали лишь полиномиальные нижние оценки вида $R(k, k) > k^c$. Экспоненциальный барьер казался непреодолимым, пока Эрдёш не отказался от попыток нарисовать конкретный граф.

Рождение вероятностного метода: схема рассуждения

Идея Эрдёша заключается в том, чтобы рассмотреть ансамбль всех возможных раскрасок как вероятностное пространство с равномерным распределением.

Пусть у нас есть полный граф $K_n$ на $n$ вершинах. Окрасим каждое из его $\binom{n}{2}$ рёбер независимо друг от друга в красный или синий цвет с равной вероятностью $p = 1/2$.

Зафиксируем некоторое подмножество вершин $S \subset V$ мощности $|S| = k$. Сколько рёбер натянуто на эти $k$ вершин? Ровно $\binom{k}{2}$. Какова вероятность того, что все эти рёбра оказались одного цвета?

1. Рёбра окрашиваются независимо, поэтому вероятность того, что все $\binom{k}{2}$ рёбер красные, равна $(1/2)^{\binom{k}{2}}$.
2. Вероятность того, что все они синие, точно такая же: $(1/2)^{\binom{k}{2}}$.
3. Так как события «все красные» и «все синие» несовместны при $k \ge 3$, вероятность монохроматичности подграфа на вершинах $S$ равна сумме их вероятностей:

$$\mathbb{P}(A_S) = \left(\frac{1}{2}\right)^{\binom{k}{2}} + \left(\frac{1}{2}\right)^{\binom{k}{2}} = 2 \cdot 2^{-\binom{k}{2}} = 2^{1 - \binom{k}{2}}$$

Здесь $A_S$ — «плохое» событие, означающее, что на подмножестве вершин $S$ образовался монохроматический $K_k$.

Теперь свяжем локальные плохие события воедино. Нас интересует вероятность того, что хотя бы для одного набора из $k$ вершин случится неприятность. Для этого привлекается фундаментальный инструмент теории вероятностей — неравенство Буля (в англоязычной литературе — Union Bound).

Для любой последовательности событий $A_1, A_2, \ldots, A_m$ (даже зависимых) вероятность их объединения не превосходит суммы их индивидуальных вероятностей:

$$\mathbb{P}\left(\bigcup_{i=1}^m A_i\right) \le \sum_{i=1}^m \mathbb{P}(A_i)$$

В отличие от формулы включений-исключений, неравенство Буля не требует независимости событий. А события $A_S$ и $A_T$ для пересекающихся наборов вершин $S$ и $T$ зависимы, ведь у них есть общие рёбра. Union bound позволяет проигнорировать эти сложные корреляции и получить верхнюю границу потерь суммированием.

Теорема Эрдёша о нижней оценке $R(k, k)$

Соберём компоненты доказательства в строгую теорему.

Теорема (Эрдёш, 1947): Если для натуральных чисел $n$ и $k$ выполняется строгое неравенство

$$\binom{n}{k} 2^{1 - \binom{k}{2}} < 1$$

то диагональное число Рамсея удовлетворяет оценке $R(k, k) > n$.

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

Обозначим через $\mathcal{F}$ семейство всех $k$-элементных подмножеств вершин графа $K_n$. Общее число таких подмножеств равно $\binom{n}{k}$.

Событие $B = \bigcup_{S \in \mathcal{F}} A_S$ означает, что в случайной раскраске существует хотя бы один монохроматический подграф $K_k$. Оценим вероятность события $B$ по неравенству Буля:

$$\mathbb{P}(B) = \mathbb{P}\left(\bigcup_{S \in \mathcal{F}} A_S\right) \le \sum_{S \in \mathcal{F}} \mathbb{P}(A_S) = \binom{n}{k} 2^{1 - \binom{k}{2}}$$

По условию теоремы эта сумма строго меньше 1:

$$\mathbb{P}(B) < 1$$

Перейдём к противоположному событию $\overline{B}$, означающему, что ни одно из плохих событий не наступило (то есть в графе нет ни красного, ни синего $K_k$):

$$\mathbb{P}(\overline{B}) = 1 - \mathbb{P}(B) > 0$$

Вероятность обнаружить раскраску без монохроматических $K_k$ строго положительна. Поскольку пространство всех раскрасок конечно, строго положительная вероятность гарантирует: среди всех $2^{\binom{n}{2}}$ вариантов раскраски существует как минимум один граф, удовлетворяющий условию. Значит, на $n$ вершинах монохроматический $K_k$ ещё не гарантирован, откуда $R(k, k) > n$. $\blacksquare$

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

Асимптотический анализ неравенства

Чтобы превратить условие теоремы $\binom{n}{k} 2^{1 - \binom{k}{2}} < 1$ в явную функцию от $k$, воспользуемся стандартной оценкой биномиального коэффициента:

$$\binom{n}{k} = \frac{n(n - 1)\ldots(n - k + 1)}{k!} \le \frac{n^k}{k!}$$

Распишем показатель степени двойки:

$$\binom{k}{2} = \frac{k(k - 1)}{2} = \frac{k^2}{2} - \frac{k}{2}$$

Тогда левая часть неравенства Эрдёша оценивается сверху:

$$\binom{n}{k} 2^{1 - \binom{k}{2}} < \frac{n^k}{k!} 2^{1 - k^2/2 + k/2} = \frac{2 \cdot 2^{k/2}}{k!} \left(\frac{n}{2^{k/2}}\right)^k$$

Мы хотим, чтобы эта величина не превосходила 1. Подставим $n = \lfloor 2^{k/2} \rfloor$. Тогда отношение $n / 2^{k/2} \le 1$, а факториал $k!$ в знаменателе с колоссальной скоростью устремляет всё выражение к нулю при $k \ge 3$.

Более точный подсчёт с использованием формулы Стирлинга ($k! \approx \sqrt{2\pi k}(k/e)^k$) даёт асимптотическую оценку:

$$R(k, k) > \frac{1 + o(1)}{e\sqrt{2}} \, k \, 2^{k/2}$$

Сравним верхнюю и нижнюю границы:

Оценка	Значение	Порядок роста	Метод доказательства
Нижняя (Эрдёш, 1947)	$R(k, k) > \frac{k}{e\sqrt{2}} 2^{k/2}$	$\Omega(k \cdot (\sqrt{2})^k)$	Вероятностный метод (Union Bound)
Верхняя (Эрдёш — Секереш, 1935)	$R(k, k) < \frac{4^k}{\sqrt{\pi k}}$	$O(k^{-1/2} \cdot 4^k)$	Индукция по вершинам графа

Основание экспоненты зажато между $\sqrt{2} \approx 1{,}414$ и $4$. За последующие десятилетия нижняя граница была улучшена Джоэлом Спенсером в константное число раз (в 2 раза с помощью локальной леммы Ловаса, которую мы разберём в одной из следующих глав), но существенно увеличить само основание экспоненты $\sqrt{2}$ не удалось до сих пор.

Почему конструктивный подход уступает случайности?

Может показаться, что вероятностный метод — это временный костыль, и со временем математики научатся строить такие графы руками. Однако история показала обратное.

Первая чисто детерминированная конструкция графа без монохроматических $K_k$ была предложена Петером Франклом и Ричардом Вильсоном только в 1981 году на основе теории пересечений множеств в векторных пространствах. Их конструкция давала нижнюю границу:

$$R(k, k) > \exp\left(c \cdot \frac{\ln^2 k}{\ln \ln k}\right)$$

Это сверхполиномиальный рост, но он катастрофически медленнее любой экспоненты $2^{c k}$. Лишь в 2015–2016 годах исследователи в области псевдослучайности и двухвходовых экстракторов (в работах Эшана Чаттопадхьяя, Дэвида Цукермана и Гила Коэна) смогли продвинуться к квазиполиномиальным и слабоэкспоненциальным конструкциям, но вероятностная граница $\sqrt{2}^k$ для явных графов остаётся недосягаемой.

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

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

Линейность математического ожидания и поиск разрезов в графах

Неравенство Буля гарантирует существование объекта, пока сумма вероятностей «плохих» событий строго меньше единицы. Но что делать, если событий слишком много, они пересекаются хаотическим образом, а их суммарная вероятность заведомо превышает единицу? В таких ситуациях вероятность избежать всех нежелательных конфигураций может казаться неизмеримо малой.

Выход из этого тупика предлагает фундаментальный принцип: случайная величина обязана хотя бы в одной точке вероятностного пространства принимать значение не меньше своего математического ожидания (и хотя бы в одной точке — не больше него). Главная сила этого утверждения кроется в алгебраическом свойстве математического ожидания: оно строго линейно даже для зависимых величин.

Абсолютная линейность и метод усреднения

Пусть на дискретном вероятностном пространстве заданы случайные величины $X_1, X_2, \dots, X_m$. Независимо от того, как именно они коррелируют друг с другом, всегда выполняется равенство:

$$\mathbb{E}\left[\sum_{i=1}^{m} X_i\right] = \sum_{i=1}^{m} \mathbb{E}[X_i]$$

Здесь $\mathbb{E}$ обозначает математическое ожидание суммы случайных величин, а правая часть представляет собой сумму их индивидуальных ожиданий. В практических задачах случайные величины чаще всего являются индикаторами событий: $X_i = \mathbb{I}_{A_i}$, где величина равна $1$, если событие $A_i$ наступило, и $0$ в противном случае. Тогда $\mathbb{E}[X_i] = \mathbb{P}(A_i)$, а математическое ожидание суммы превращается в сумму вероятностей элементарных событий.

Из линейности немедленно следует базисный принцип вероятностного существования:

Если случайная величина $X$ имеет математическое ожидание $\mathbb{E}[X] = \mu$, то в вероятностном пространстве непременно существуют элементарные исходы $\omega_1$ и $\omega_2$ такие, что $X(\omega_1) \geq \mu$ и $X(\omega_2) \leq \mu$.

Если бы случайная величина во всех точках пространства строго превосходила $\mu$ (или строго уступала ему), то и среднее значение строго отличалось бы от $\mu$, что невозможно. Это простое соображение позволяет доказывать существование структур рекордного размера без какого-либо анализа совместных распределений.

Двудольные подграфы и задача о максимальном разрезе

Классическая NP-трудная задача комбинаторной оптимизации — поиск максимального разреза (Max-Cut): требуется разбить множество вершин графа на два непересекающихся класса так, чтобы число рёбер между ними оказалось как можно больше.

Пусть задан произвольный граф $G = (V, E)$ с $n$ вершинами и $m$ рёбрами. Какую гарантированную долю рёбер можно перевести в двудольный подграф?

Построим вероятностное пространство. Для каждой вершины $v \in V$ подбросим честную монету: с вероятностью $1/2$ отправим её во множество $A$, а с вероятностью $1/2$ — во множество $B = V \setminus A$. Выборы для всех вершин делаем взаимно независимыми.

Ребро $e = \{u, v\} \in E$ попадает в разрез (то есть соединяет доли $A$ и $B$) тогда и только тогда, когда его концы оказываются в разных множествах. Введём индикатор для каждого ребра $e \in E$:

$$X_e = \begin{cases} 1, & \text{если } (u \in A \land v \in B) \lor (u \in B \land v \in A), \\ 0, & \text{иначе.} \end{cases}$$

Найдём вероятность того, что ребро пересекает разрез:

$$\mathbb{P}(X_e = 1) = \mathbb{P}(u \in A) \cdot \mathbb{P}(v \in B) + \mathbb{P}(u \in B) \cdot \mathbb{P}(v \in A) = \frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{2}$$

Общее число рёбер в разрезе задаётся суммой индикаторов $X = \sum_{e \in E} X_e$. Применяя линейность математического ожидания, получаем:

$$\mathbb{E}[X] = \sum_{e \in E} \mathbb{E}[X_e] = \sum_{e \in E} \frac{1}{2} = \frac{m}{2}$$

События $\{X_e = 1\}$ для смежных рёбер явно зависимы: если ребро $\{u, v\}$ уже лежит в разрезе, то положение вершины $v$ фиксировано относительно $u$, что меняет условную вероятность пересечения разреза ребром $\{v, w\}$. Однако линейность математического ожидания игнорирует эти корреляции.

Так как $\mathbb{E}[X] = m/2$, в графе гарантированно существует разбиение вершин $V = A \cup B$, при котором разрез содержит не менее $m/2$ рёбер.

Любой граф $G$ с $m$ рёбрами содержит двудольный подграф, в котором сосредоточено по меньшей мере $\lceil m/2 \rceil$ рёбер. Классический результат Пала Эрдёша показывает, что оценку можно усилить: в любом связном графе с $m$ рёбрами и $n$ вершинами существует двудольный подграф, содержащий не менее $\frac{m}{2} + \frac{n-1}{4}$ рёбер (а если все вершины имеют чётные степени $d_v = 2k_v$, то не менее $\frac{m}{2} + \frac{c(G)}{2}$, где $c(G)$ — число компонент связности).

Пути в турнирах: когда комбинаторика бессильна без усреднения

Рассмотрим ориентированный граф, в котором между каждой парой вершин проведено ровно одно направленное ребро — турнир $T = (V, E)$ на $n$ вершинах. Гамильтоновым путём называется простой ориентированный путь, проходящий через все $n$ вершин ровно по одному разу.

Теорема Редеи утверждает, что в любом турнире существует хотя бы один гамильтонов путь. Но сколько таких путей может существовать одновременно? Пусть $P(n)$ — максимальное по всем турнирам на $n$ вершинах число гамильтоновых путей. Задача нахождения точного значения $P(n)$ чрезвычайно сложна, но с помощью математического ожидания венгерский математик Тибор Селе (Tibor Szele) в 1943 году доказал фундаментальную нижнюю оценку.

Рассмотрим случайный турнир $T_n$, в котором ориентация каждого из $\binom{n}{2}$ рёбер выбирается подбрасыванием правильной монеты: ребро $(u, v)$ направлено от $u$ к $v$ с вероятностью $1/2$, и от $v$ к $u$ с вероятностью $1/2$ независимо для всех пар.

Всего существует ровно $n!$ упорядоченных последовательностей из всех вершин графа: $\sigma = (v_1, v_2, \dots, v_n)$. Для каждой фиксированной перестановки $\sigma$ введём индикаторную величину:

$$I_\sigma = \begin{cases} 1, & \text{если ребра } (v_1, v_2), (v_2, v_3), \dots, (v_{n-1}, v_n) \text{ направлены в соответствии с порядком}, \\ 0, & \text{иначе.} \end{cases}$$

Путь содержит ровно $n - 1$ конкретное ребро. Так как все пары ориентируются независимо, вероятность того, что все эти $n - 1$ дуг согласованы с перестановкой $\sigma$, равна:

$$\mathbb{P}(I_\sigma = 1) = \left(\frac{1}{2}\right)^{n-1}$$

Суммарное число гамильтоновых путей $H$ в случайном турнире выражается суммой индикаторов по всем $n!$ перестановкам:

$$H = \sum_{\sigma \in S_n} I_\sigma$$

По линейности математического ожидания:

$$\mathbb{E}[H] = \sum_{\sigma \in S_n} \mathbb{E}[I_\sigma] = n! \cdot 2^{-(n-1)}$$

Здесь корреляции между путями выражены максимально сильно: два пути могут перекрываться по $n-2$ рёбрам или не иметь общих рёбер вовсе. Тем не менее линейность обошла всю топологическую сложность пересечения путей.

Следовательно, существует турнир на $n$ вершинах, содержащий не менее $n! / 2^{n-1}$ ориентированных гамильтоновых путей. Это экспоненциально большая величина: по формуле Стирлинга она растёт асимптотически как $\sqrt{2\pi n} \cdot (n / (2e))^n \cdot 2$.

От вероятности к алгоритму: метод условных математических ожиданий

Доказательство через математическое ожидание утверждает: «объект существует». Но как найти конкретный разрез размера $\geq m/2$, не перебирая все $2^n$ возможных подмножеств?

Случайный выбор даёт рандомизированный алгоритм: поскольку среднее равно $m/2$, случайная раскраска вершин даёт подходящий разрез со значительной вероятностью. Однако существует строгий способ превратить это рассуждение в детерминированный полиномиальный алгоритм. Этот приём называется методом условных математических ожиданий (дерандомизацией).

Пусть вершины графа упорядочены: $v_1, v_2, \dots, v_n$. Мы будем последовательно фиксировать принадлежность каждой вершины $v_i$ множеству $A$ или множеству $B$.

Обозначим через $x_i \in \{A, B\}$ решение для вершины $v_i$. На шаге $k$ уже зафиксированы положения вершин $v_1, \dots, v_k$, а остальные $n - k$ вершин всё ещё выбирают доли случайно с вероятностями $1/2$. Определим условное математическое ожидание размера разреза:

$$E(x_1, \dots, x_k) = \mathbb{E}[X \mid v_1 = x_1, \dots, v_k = x_k]$$

По формуле полного математического ожидания:

$$E(x_1, \dots, x_{k-1}) = \frac{1}{2} E(x_1, \dots, x_{k-1}, A) + \frac{1}{2} E(x_1, \dots, x_{k-1}, B)$$

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

$$\max \Big( E(x_1, \dots, x_{k-1}, A), \; E(x_1, \dots, x_{k-1}, B) \Big) \geq E(x_1, \dots, x_{k-1})$$

Пошаговый алгоритм

1. В начальный момент вершины не зафиксированы, условное ожидание совпадает с безусловным: $E(\emptyset) = m/2$.
2. Для шага $k$ от $1$ до $n$: вычисляем оба значения $E(x_1, \dots, x_{k-1}, A)$ и $E(x_1, \dots, x_{k-1}, B)$.
3. Выбираем для вершины $v_k$ ту долю, которая максимизирует условное ожидание (или любую из них при равенстве).
4. К шагу $n$ все вершины распределены: случайности не осталось, а итоговый размер полученного разреза удовлетворяет цепи неравенств:

$$|E(A, B)| = E(x_1, \dots, x_n) \geq E(x_1, \dots, x_{n-1}) \geq \dots \geq E(\emptyset) = \frac{m}{2}$$

Вычисление условного ожидания за константное время

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

Категория ребра	Статус концов $u$ и $v$	Вклад в $E(x_1, \dots, x_k)$
Уже разрезанные	Оба конца среди $\{v_1, \dots, v_k\}$, лежат в разных долях	Ровно $1$
Монохроматические	Оба конца среди $\{v_1, \dots, v_k\}$, лежат в одной доле	Ровно $0$
Неопределённые	Хотя бы один конец ещё не зафиксирован (в $\{v_{k+1}, \dots, v_n\}$)	Ровно $1/2$

При принятии решения для вершины $v_k$ вклад рёбер, оба конца которых не включают $v_k$, вообще не меняется. Значение меняют исключительно рёбра, связывающие $v_k$ с уже размещёнными соседями $v_j$ ($j < k$):

• Если поместить $v_k$ в $A$, то в разрез попадут все рёбра к уже размещённым соседям из $B$.
• Если поместить $v_k$ в $B$, то в разрез попадут все рёбра к уже размещённым соседям из $A$.

Решение тривиально: жадно отправляем вершину $v_k$ в то множество, где у неё меньше соседей на текущем шаге. Это максимизирует прирост числа рёбер в разрезе и гарантирует итоговый размер не менее $m/2$ за время $O(n + m)$.

Баланс сумм векторов: пример Спенсера

Линейность математического ожидания работает не только с дискретными индикаторами в графах, но и в евклидовых пространствах. Классическая задача комбинаторной геометрии — балансировка векторов.

Пусть $v_1, v_2, \dots, v_n \in \mathbb{R}^n$ — векторы единичной длины: $\|v_i\| = 1$. Требуется выбрать знаки $\epsilon_1, \epsilon_2, \dots, \epsilon_n \in \{-1, +1\}$ так, чтобы вектор суммы $\sum_{i=1}^{n} \epsilon_i v_i$ оказался как можно меньше по норме.

В качестве случайной величины рассмотрим квадрат евклидовой длины:

$$X = \left\| \sum_{i=1}^{n} \epsilon_i v_i \right\|^2 = \left( \sum_{i=1}^{n} \epsilon_i v_i, \sum_{j=1}^{n} \epsilon_j v_j \right) = \sum_{i=1}^{n} \sum_{j=1}^{n} \epsilon_i \epsilon_j (v_i, v_j)$$

Здесь $(v_i, v_j)$ обозначает стандартное скалярное произведение. Выберем каждый знак $\epsilon_i$ независимо с равными вероятностями $\mathbb{P}(\epsilon_i = +1) = \mathbb{P}(\epsilon_i = -1) = 1/2$.

Вычислим математическое ожидание произведения знаков $\epsilon_i \epsilon_j$:

• При $i = j$: $\epsilon_i^2 = 1$ детерминированно, поэтому $\mathbb{E}[\epsilon_i^2] = 1$.
• При $i \neq j$: в силу независимости $\mathbb{E}[\epsilon_i \epsilon_j] = \mathbb{E}[\epsilon_i] \cdot \mathbb{E}[\epsilon_j] = 0 \cdot 0 = 0$.

Раскрываем математическое ожидание квадрата нормы по свойству линейности:

$$\mathbb{E}[X] = \sum_{i=1}^{n} \sum_{j=1}^{n} \mathbb{E}[\epsilon_i \epsilon_j] (v_i, v_j) = \sum_{i=1}^{n} \mathbb{E}[\epsilon_i^2] \|v_i\|^2 + \sum_{i \neq j} \mathbb{E}[\epsilon_i \epsilon_j] (v_i, v_j) = \sum_{i=1}^{n} 1 \cdot 1 + 0 = n$$

Так как среднее значение квадрата длины вектора равно $n$, существует такой набор знаков $\epsilon_1, \dots, \epsilon_n$, для которого:

$$\left\| \sum_{i=1}^{n} \epsilon_i v_i \right\|^2 \leq n \implies \left\| \sum_{i=1}^{n} \epsilon_i v_i \right\| \leq \sqrt{n}$$

Одновременно с этим существует и выбор знаков, дающий норму не менее $\sqrt{n}$. Геометрическая интерференция векторов в среднем полностью взаимно гасит недиагональные проекции.

Метод удаления: двухшаговые вероятностные конструкции

Чисто случайный объект почти никогда не бывает идеальным. Если бросить симметричную монету для каждого ребра графа, стремясь избежать монохроматических клик или коротких циклов, редкие нежелательные конфигурации почти наверняка появятся. В базовом вероятностном методе мы требовали, чтобы вероятность появления хотя бы одного дефекта была строго меньше единицы. Но что делать, если пространство исходов устроено так, что математическое ожидание числа дефектов заведомо велико, и «чистый» объект случайным выбором получить невозможно?

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

Архитектура метода: генерация плюс хирургия

В классическом вероятностном доказательстве существования объекта со свойством $\mathcal{P}$ мы задаём вероятностное пространство и показываем, что $\mathbb{P}(\text{объект обладает } \mathcal{P}) > 0$. Если дефекты описываются событиями $A_1, A_2, \dots, A_m$, то объединение $\bigcup A_i$ не должно покрывать всё пространство. Метод линейности математического ожидания расширил эту оптику: мы научились находить объекты, где число дефектов или целевая функция не хуже среднего значения.

Метод удаления превращает вероятностное рассуждение в двухшаговый алгоритм:

1. Случайный шаг (генерация с запасом): конструируется случайный сырой объект $X_0$ с параметрами, оптимизированными под плотность целевых элементов (например, рёбер или вершин). Параметры выбираются агрессивно: мы сознательно разрешаем возникновение дефектов, если их суммарное математическое ожидание оказывается существенно меньше объёма полезной структуры.
2. Детерминированный шаг (хирургия): для каждого возникшего дефекта детерминированно удаляется один элемент (вершина или ребро), разрушающий запрещённую конфигурацию.

В результате мы гарантированно получаем очищенный объект $X$, в котором дефектов нет вовсе, а число оставшихся полезных элементов строго положительно.

Поскольку число удаляемых элементов точно равно числу дефектов (или даже меньше, если одно удаление устраняет сразу несколько нарушений), размер итогового объекта оценивается снизу через линейность математического ожидания.

Нижняя оценка числа независимости: баланс между плотностью и дефектами

Пусть дан граф $G = (V, E)$ с $n$ вершинами и $m$ рёбрами со средней степенью $d = 2m / n$. Напомним, что независимым множеством называется подмножество вершин, между которыми нет ни одного ребра. Обозначим через $\alpha(G)$ размер наибольшего независимого множества. Какую нижнюю оценку на $\alpha(G)$ гарантирует метод удаления?

Построим независимое множество в два шага:

1. Создадим случайное подмножество $S_0 \subseteq V$, выбирая каждую вершину независимо с некоторой фиксированной вероятностью $p \in (0, 1)$.
2. Множество $S_0$ ещё не является независимым: некоторые рёбра графа $G$ оказались целиком внутри $S_0$. Для каждого такого ребра $\{u, v\} \in E(G)$ удалим из $S_0$ одну из его вершин (любую, например $u$).

Оставшееся подмножество $S \subseteq S_0$ по построению не содержит ни одного ребра из $E(G)$, то есть образует корректное независимое множество.

Оценим размер полученного множества $S$. Пусть $X$ — число вершин, попавших в $S_0$, а $Y$ — число рёбер графа $G$, оба конца которых попали в $S_0$. При удалении по одной вершине на каждое ребро мы удалим не более $Y$ вершин. Следовательно:

$$|S| \geq X - Y$$

Здесь $X$ — случайное число исходных вершин, $Y$ — число возникших дефектов (внутренних рёбер), а $|S|$ — число уцелевших вершин после чистки.

Вычислим математическое ожидание обеих величин, пользуясь линейностью математического ожидания:

$$\mathbb{E}[X] = \sum_{v \in V} \mathbb{P}(v \in S_0) = n p$$

Для произвольного ребра $e = \{u, v\} \in E$ оба конца попадают в $S_0$ с вероятностью $p^2$, так как выбор вершин независим:

$$\mathbb{E}[Y] = \sum_{e \in E} \mathbb{P}(u \in S_0 \text{ и } v \in S_0) = m p^2$$

Подставляя ожидания в неравенство для $|S|$:

$$\mathbb{E}[|S|] \geq \mathbb{E}[X] - \mathbb{E}[Y] = n p - m p^2$$

Поскольку математическое ожидание величины $|S|$ равно $n p - m p^2$, в пространстве исходов обязан существовать хотя бы один конкретный выбор подмножества $S_0$, дающий размер очищенного множества не меньше среднего:

$$\alpha(G) \geq n p - m p^2$$

Величина $p$ была произвольным параметром в диапазоне $(0, 1)$. Найдём значение $p$, максимизирующее квадратичную функцию $f(p) = n p - m p^2$. Производная $f'(p) = n - 2m p$ обращается в ноль в точке:

$$p^* = \frac{n}{2m} = \frac{1}{d}$$

При таком выборе вероятности (при условии $d \geq 1$, иначе граф содержит изолированные вершины и задача тривиальна) получаем оценку:

$$\alpha(G) \geq n \left(\frac{1}{d}\right) - m \left(\frac{1}{d^2}\right) = \frac{n}{d} - \frac{m}{4m^2 / n^2} = \frac{n}{d} - \frac{n^2}{4m} = \frac{n}{d} - \frac{n}{2d} = \frac{n}{2d}$$

Теорема о независимом множестве: В любом графе со средней степенью $d \geq 1$ существует независимое множество размера не менее $\frac{n}{2d}$.

Если в графе на 1000 вершинах средняя степень вершин равна 10, то подстановка $p = 1/10$ в среднем даёт 100 выбранных вершин и $5000 \times (0.01) = 50$ индуцированных рёбер. Удалив по одной вершине для каждого ребра, мы гарантированно сохраняем независимое множество из как минимум 50 вершин.

Разрешение парадокса: обхват против хроматического числа

Классическая интуиция теории графов подсказывает: чтобы граф имел высокое хроматическое число $\chi(G)$ (минимальное число цветов для правильной раскраски вершин, при которой смежные вершины разного цвета), в нём должно быть много плотных локальных сгустков — клик или коротких нечётных циклов. Если же в графе вовсе нет коротких циклов, локально любая окрестность вершины выглядит как дерево, которое раскрашивается всего в 2 цвета.

Напомним, что обхватом (girth) графа называют длину его наименьшего простого цикла. Казалось естественным предположить, что при высоком обхвате глобальное хроматическое число не может расти неограниченно.

В 1959 году Пал Эрдёш сокрушил эту гипотезу одной из самых изящных статей в истории комбинаторики, применив метод удаления.

Теорема Эрдёша (1959): Для любых натуральных чисел $k \geq 3$ и $g \geq 3$ существует граф $G$, у которого одновременно:

1. Обхват $\text{girth}(G) > g$.
2. Хроматическое число $\chi(G) > k$.

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

Шаг 1. Случайная модель и компромисс плотности

Рассмотрим случайный граф Эрдеша — Реньи $G(n, p)$ на $n$ вершинах, где каждое из $\binom{n}{2}$ рёбер проводится независимо с вероятностью $p$.

Перед нами стоят два противоположных требования:

• Чтобы уничтожить все циклы длины $\leq g$, рёбер должно быть мало (низкая вероятность $p$).
• Чтобы хроматическое число $\chi(G)$ было большим, число независимости $\alpha(G)$ должно быть малым, так как в любой правильной раскраске каждый цветовой класс — это независимое множество. Из очевидного соотношения:

  $$\chi(G) \geq \frac{n}{\alpha(G)}$$

  следует: если мы добьёмся $\alpha(G) < \frac{n}{k}$, то автоматически получим $\chi(G) > k$. Но чтобы число независимости было малым, граф обязан быть достаточно плотным, то есть рёбер должно быть много (высокая вероятность $p$).

Искусство метода удаления — найти узкий коридор для $p(n)$, где плотность рёбер уже подавляет большие независимые множества, но число коротких циклов всё ещё растёт медленнее, чем число вершин.

Зафиксируем параметр $\theta \in (0, 1/g)$ и положим:

$$p = n^{\theta - 1}$$

Так как $\theta < 1/g < 1$, вероятность $p$ стремится к нулю при $n \to \infty$, но произведение $n p = n^\theta$ стремится к бесконечности.

Шаг 2. Подсчёт коротких циклов

Пусть $C$ — число циклов длины не более $g$ в случайном графе $G(n, p)$. Любой цикл длины $j$ (где $3 \leq j \leq g$) задаётся упорядоченным набором из $j$ вершин. Число способов выбрать такой цикл в полном графе $K_n$ равно:

$$\frac{n(n-1)\dots(n-j+1)}{2j} \leq \frac{n^j}{2j}$$

Каждый такой цикл присутствует в $G(n, p)$ с вероятностью $p^j$. В силу линейности математического ожидания:

$$\mathbb{E}[C] = \sum_{j=3}^{g} \frac{n^j}{2j} p^j \leq \sum_{j=3}^{g} n^j (n^{\theta - 1})^j = \sum_{j=3}^{g} n^{j \theta}$$

Поскольку $\theta < 1/g$, показатель степени $j \theta \leq g \theta < 1$. Наибольшее слагаемое в сумме достигается при $j = g$:

$$\mathbb{E}[C] \leq g \cdot n^{g \theta} = o(n)$$

Математическое ожидание числа коротких циклов растёт строго медленнее, чем $n$. Применим неравенство Маркова: для любой неотрицательной случайной величины $\mathbb{P}(C \geq n/2) \leq \frac{\mathbb{E}[C]}{n/2}$. Следовательно:

$$\mathbb{P}\left(C \geq \frac{n}{2}\right) \leq \frac{2 g n^{g \theta}}{n} = 2 g n^{g \theta - 1} \to 0 \quad \text{при } n \to \infty$$

Значит, с вероятностью, стремящейся к 1, число коротких циклов в графе не превышает $n/2$:

$$\mathbb{P}\left(C < \frac{n}{2}\right) > \frac{1}{2} \quad \text{(для достаточно больших } n\text{)}$$

Шаг 3. Контроль числа независимости

Теперь оценим вероятность того, что в графе найдётся независимое множество размера $r = \lceil \frac{n}{2k} \rceil$.

Для фиксированного подмножества из $r$ вершин вероятность того, что между ними нет ни одного ребра, равна $(1 - p)^{\binom{r}{2}}$. Число таких подмножеств равно $\binom{n}{r}$. Оценим вероятность существования хотя бы одного независимого множества размера $r$ через неравенство Буля:

$$\mathbb{P}(\alpha(G) \geq r) \leq \binom{n}{r} (1 - p)^{\binom{r}{2}}$$

Воспользуемся стандартными оценками $\binom{n}{r} \leq \left(\frac{e n}{r}\right)^r$ и $1 - p \leq e^{-p}$:

$$\mathbb{P}(\alpha(G) \geq r) \leq \left(\frac{e n}{r}\right)^r e^{-p r (r - 1) / 2} = \left(\frac{e n}{r} \cdot e^{-p (r - 1) / 2}\right)^r$$

Подставим значения $r \approx \frac{n}{2k}$ и $p = n^{\theta - 1}$:

$$\frac{e n}{r} \approx 2 e k = \text{const}$$

Показатель экспоненты:

$$\frac{p (r - 1)}{2} \approx \frac{n^{\theta - 1} \cdot n}{4k} = \frac{n^\theta}{4k} \to \infty \quad \text{при } n \to \infty$$

Следовательно, выражение под знаком степени стремится к нулю:

$$\frac{e n}{r} \cdot e^{-p (r - 1) / 2} \to 0$$

Отсюда вероятность существования независимого множества размера $r$ стремительно убывает:

$$\mathbb{P}(\alpha(G) \geq r) \to 0 \quad \text{при } n \to \infty$$

Для достаточно больших $n$ эта вероятность строго меньше $1/2$.

Шаг 4. Детерминированная чистка

Объединим результаты двух шагов. Так как:

$$\mathbb{P}\left(C \geq \frac{n}{2}\right) < \frac{1}{2} \quad \text{и} \quad \mathbb{P}(\alpha(G) \geq r) < \frac{1}{2}$$

По неравенству Буля вероятность того, что нарушится хотя бы одно из условий, строго меньше $1/2 + 1/2 = 1$. Следовательно, существует исход — конкретный граф $G_0$ на $n$ вершинах, для которого одновременно выполнены два свойства:

1. Число коротких циклов $C < n/2$.
2. Размер наибольшего независимого множества $\alpha(G_0) < r = \lceil \frac{n}{2k} \rceil$.

Теперь проведём операцию удаления: из каждого цикла длины $\leq g$ удалим ровно по одной вершине. Обозначим полученный индуцированный подграф через $G^*$.

Проверим свойства очищенного графа $G^*$:

• Обхват: мы разрушили абсолютно все циклы длины $\leq g$, удалив из каждого хотя бы одну вершину. Следовательно, в $G^*$ нет циклов длины $\leq g$, и $\text{girth}(G^*) > g$.
• Число вершин: поскольку всего циклов было $C < n/2$, мы удалили строго меньше $n/2$ вершин. Число вершин графа $G^*$ составляет:

  $$|V(G^*)| = n - C > n - \frac{n}{2} = \frac{n}{2}$$

• Хроматическое число: подграф не может иметь число независимости больше, чем исходный граф, ведь любое независимое множество в $G^*$ уже было независимым множеством в $G_0$. Значит:

  $$\alpha(G^*) \leq \alpha(G_0) < \frac{n}{2k}$$

  Оценим хроматическое число $G^*$:

  $$\chi(G^*) \geq \frac{|V(G^*)|}{\alpha(G^*)} > \frac{n / 2}{n / (2k)} = k$$

Мы сконструировали граф $G^*$, у которого обхват строго больше $g$, а хроматическое число строго больше $k$.

Границы применимости: когда удаления недостаточно

Метод удаления демонстрирует поразительную силу там, где дефекты носят разреженный характер. Если математическое ожидание числа нарушений составляет $o(n)$ (или в более общем смысле строго меньше масштаба целевого множества), простая поштучная ликвидация дефектов почти не меняет глобальных характеристик системы.

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

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

Метод второго момента и пороговые свойства случайных графов

Математическое ожидание неотрицательной целочисленной случайной величины способно уходить в бесконечность, пока вероятность встретить хотя бы один ненулевой исход стремительно падает до нуля. Достаточно представить величину $X$, принимающую гигантское значение $M = 2^n$ с ничтожной вероятностью $2^{-n/2}$, а в остальных случаях равную нулю: её среднее $\mathbb{E}[X] = 2^{n/2} \to \infty$, однако событие $X > 0$ наступает лишь с исчезающей вероятностью $2^{-n/2} \to 0$. Первого момента категорически недостаточно, чтобы гарантировать существование объекта в типичном графе, если дисперсия раздувает хвосты распределения.

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

От математического ожидания к концентрации: неравенство Чебышёва

Если исследуется случайная величина $X \geq 0$, принимающая целые неотрицательные значения (например, число копий заданного подграфа в случайном графе $G(n, p)$), равенство $X = 0$ означает, что объект не реализовался. Задача состоит в том, чтобы строго доказать: при определённых параметрах графа $\mathbb{P}(X = 0) \to 0$ при $n \to \infty$.

Оценка снизу на вероятность появления объекта через первый и второй моменты выводится напрямую из классического неравенства Чебышёва:

$$\mathbb{P}(|X - \mathbb{E}[X]| \geq \mathbb{E}[X]) \leq \frac{\mathrm{Var}(X)}{(\mathbb{E}[X])^2}$$

Поясним каждый элемент:

• $X$ — целочисленная неотрицательная случайная величина (число искомых конфигураций).
• $\mathbb{E}[X]$ — математическое ожидание величины $X$.
• $\mathrm{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$ — дисперсия величины $X$, измеряющая средний квадрат отклонения от центра.
• Событие $|X - \mathbb{E}[X]| \geq \mathbb{E}[X]$ означает, что отклонение величины влево или вправо от среднего не меньше самого среднего. Поскольку $X \geq 0$, попадание в левый хвост ($X - \mathbb{E}[X] \leq -\mathbb{E}[X]$) эквивалентно в точности исходу $X \leq 0$, то есть $X = 0$.

Следовательно, вероятность ненаступления события ограничена сверху:

$$\mathbb{P}(X = 0) \leq \mathbb{P}(|X - \mathbb{E}[X]| \geq \mathbb{E}[X]) \leq \frac{\mathrm{Var}(X)}{(\mathbb{E}[X])^2}$$

Ключевой принцип метода второго момента: Если для неотрицательной случайной величины $X$ выполнено предельное соотношение $\mathrm{Var}(X) = o((\mathbb{E}[X])^2)$ при $n \to \infty$, то $\mathbb{P}(X = 0) \to 0$, а значит, $\mathbb{P}(X > 0) \to 1$. В этом случае говорят, что свойство выполняется асимптотически почти наверное (a.a.s. — asymptotically almost surely).

Анатомия дисперсии суммы индикаторов

В комбинаторных задачах величина $X$ практически всегда раскладывается в сумму индикаторов:

$$X = \sum_{i \in \mathcal{I}} X_i$$

где $\mathcal{I}$ — семейство потенциальных мест размещения структуры (например, все возможные наборы из $k$ вершин), а $X_i = 1$, если на $i$-м наборе подграф действительно реализовался, и $X_i = 0$ в противном случае.

В отличие от вычисления математического ожидания $\mathbb{E}[X] = \sum \mathbb{E}[X_i]$, где зависимость слагаемых не играла роли, дисперсия напрямую вскрывает парные корреляции:

$$\mathrm{Var}(X) = \sum_{i \in \mathcal{I}} \mathrm{Var}(X_i) + \sum_{i \neq j} \mathrm{Cov}(X_i, X_j)$$

Для каждого индикатора $X_i$:

$$\mathrm{Var}(X_i) = \mathbb{E}[X_i^2] - (\mathbb{E}[X_i])^2 = \mathbb{P}(X_i = 1) - (\mathbb{P}(X_i = 1))^2 \leq \mathbb{P}(X_i = 1) = \mathbb{E}[X_i]$$

Сумма дисперсий отдельных слагаемых тривиально ограничивается сверху первым моментом:

$$\sum_{i \in \mathcal{I}} \mathrm{Var}(X_i) \leq \mathbb{E}[X]$$

Если $\mathbb{E}[X] \to \infty$, то эта часть в отношении к $(\mathbb{E}[X])^2$ исчезает: $\frac{\mathbb{E}[X]}{(\mathbb{E}[X])^2} = \frac{1}{\mathbb{E}[X]} \to 0$.

Вся тяжесть анализа переносится на ковариации:

$$\mathrm{Cov}(X_i, X_j) = \mathbb{E}[X_i X_j] - \mathbb{E}[X_i] \mathbb{E}[X_j] = \mathbb{P}(X_i = 1 \wedge X_j = 1) - \mathbb{P}(X_i = 1)\mathbb{P}(X_j = 1)$$

В модели Эрдёша — Реньи $G(n, p)$ рёбра возникают независимо. Если две структуры $i$ и $j$ не разделяют ни одного общего ребра, события $X_i = 1$ и $X_j = 1$ независимы, откуда $\mathrm{Cov}(X_i, X_j) = 0$.

Ковариация строго положительна лишь тогда, когда подграфы делят общие рёбра. Обозначим отношение зависимости между индексами как $i \sim j$ ($i \neq j$, подграфы пересекаются хотя бы по одному ребру). Тогда:

$$\sum_{i \neq j} \mathrm{Cov}(X_i, X_j) \leq \sum_{i \sim j} \mathbb{E}[X_i X_j] = \sum_{i \in \mathcal{I}} \mathbb{P}(X_i = 1) \sum_{j \sim i} \mathbb{P}(X_j = 1 \mid X_i = 1)$$

Из соображений симметрии графа величина $\Delta^* = \sum_{j \sim i} \mathbb{P}(X_j = 1 \mid X_i = 1)$ одинакова для любого фиксированного индекса $i$. Тогда сумма сворачивается:

$$\sum_{i \sim j} \mathbb{E}[X_i X_j] = \mathbb{E}[X] \cdot \Delta^*$$

Деля на $(\mathbb{E}[X])^2$, получаем компактный операционный критерий метода второго момента:

$$\frac{\mathrm{Var}(X)}{(\mathbb{E}[X])^2} \leq \frac{1}{\mathbb{E}[X]} + \frac{\Delta^*}{\mathbb{E}[X]}$$

Чтобы доказать, что $X > 0$ почти наверное, необходимо проверить выполнение двух условий:

1. $\mathbb{E}[X] \to \infty$;
2. $\Delta^* = o(\mathbb{E}[X])$.

Пороговые функции вероятности

В детерминированных графах добавление рёбер меняет топологию дискретными шагами. В модели $G(n, p)$, где каждое из $\binom{n}{2}$ рёбер включается независимо с вероятностью $p = p(n)$, монотонные свойства графа ведут себя качественно иначе: возникает эффект резкого фазового перехода.

Определение пороговой функции: Функция $r(n)$ называется пороговой (threshold) для монотонного возрастающего свойства $\mathcal{P}$ в модели $G(n, p)$, если:

$$\lim_{n \to \infty} \mathbb{P}(G(n, p) \in \mathcal{P}) = \begin{cases} 0, & \text{если } p(n) = o(r(n)) \\ 1, & \text{если } r(n) = o(p(n)) \end{cases}$$

Доказательство порога всегда двустороннее и реализуется через тандем методов:

• Метод первого момента (0-закон): если $p(n) \ll r(n)$, доказывается, что $\mathbb{E}[X] \to 0$. По неравенству Маркова $\mathbb{P}(X \geq 1) \leq \mathbb{E}[X] \to 0$, то есть подграфов нет a.a.s.
• Метод второго момента (1-закон): если $p(n) \gg r(n)$, проверяется, что $\mathbb{E}[X] \to \infty$ и $\Delta^* = o(\mathbb{E}[X])$, что гарантирует $\mathbb{P}(X = 0) \to 0$, то есть подграф присутствует a.a.s.

Порог появления треугольника: детальный расчёт

Продемонстрируем работу связки первого и второго моментов на базовой структурной единице — цикле длины 3 ($K_3$).

Пусть $X$ — число копий $K_3$ в графе $G(n, p)$. Всего возможных троек вершин $\binom{n}{3}$. Для каждой тройки $i$ индикатор $X_i = 1$, если все 3 ребра между ними присутствуют, с вероятностью $\mathbb{P}(X_i = 1) = p^3$.

Шаг 1: Математическое ожидание и гипотеза о пороге

$$\mathbb{E}[X] = \binom{n}{3} p^3 = \frac{n(n-1)(n-2)}{6} p^3 \sim \frac{n^3 p^3}{6}$$

Поведение $\mathbb{E}[X]$ критически зависит от скорости убывания $p(n)$:

• Если $p(n) = o(1/n)$, то $n p \to 0$, откуда $\mathbb{E}[X] \to 0$. По методу первого момента $\mathbb{P}(X \geq 1) \to 0$.
• Если $p(n) \gg 1/n$, то $n p \to \infty$, откуда $\mathbb{E}[X] \to \infty$.

Кандидат на пороговую функцию найден: $r(n) = 1/n$. Теперь необходимо доказать, что при $p(n) \gg 1/n$ треугольники действительно обязаны появиться.

Шаг 2: Классификация пересечений и оценка ковариации

Зафиксируем конкретный треугольник $i = \{u, v, w\}$. Рассмотрим произвольный другой треугольник $j$ и классифицируем их возможное взаимное расположение:

| Пересечение по вершинам $|V(i) \cap V(j)|$ | Число общих рёбер | Число способов выбрать $j$ | $\mathbb{P}(X_j = 1 \mid X_i = 1)$ | Вклад в $\Delta^*$ | |---|---|---|---|---| | $0$ или $1$ | $0$ | $\binom{n-3}{3} + 3\binom{n-3}{2}$ | $p^3$ | $0$ (не входят в $j \sim i$) | | $2$ | $1$ | $3 \cdot (n - 3)$ | $p^2$ | $O(n p^2)$ | | $3$ | $3$ | совпадает с $i$ | — | не учитывается ($j \neq i$) |

Два различных треугольника могут делить либо 0 рёбер (если у них 0 или 1 общая вершина), либо ровно 1 ребро (если у них 2 общие вершины). Разделить сразу 2 ребра они не могут: любые два ребра треугольника содержат все три его вершины, что однозначно задает сам треугольник.

Следовательно, сумма условных вероятностей по зависимым индексам содержит только слагаемые с одним общим ребром:

$$\Delta^* = \sum_{j \sim i} \mathbb{P}(X_j = 1 \mid X_i = 1) = 3(n - 3) \cdot p^2 = O(n p^2)$$

Поясним множители: $3$ — способ выбрать общее ребро в треугольнике $i$, $(n - 3)$ — способ выбрать третью вершину треугольника $j$, $p^2$ — вероятность появления двух оставшихся рёбер треугольника $j$ (общее ребро уже гарантированно присутствует в условии $X_i = 1$).

Шаг 3: Проверка условия сходимости

Сопоставим $\Delta^*$ с математическим ожиданием:

$$\frac{\Delta^*}{\mathbb{E}[X]} = \frac{\Theta(n p^2)}{\Theta(n^3 p^3)} = \Theta\left(\frac{1}{n^2 p}\right)$$

При $p(n) \gg 1/n$ подставим худший случай: пусть $p(n) = \omega(n) / n$, где $\omega(n) \to \infty$ сколь угодно медленно. Тогда:

$$\frac{1}{n^2 p} = \frac{1}{n^2 \cdot \frac{\omega(n)}{n}} = \frac{1}{n \cdot \omega(n)} \to 0$$

Отношение стремится к нулю с запасом (для обращения дроби в ноль было бы достаточно даже $p \gg n^{-2}$, однако условие $\mathbb{E}[X] \to \infty$ требует $p \gg n^{-1}$).

Таким образом, при $p(n) \gg 1/n$ выполнено:

$$\frac{\mathrm{Var}(X)}{(\mathbb{E}[X])^2} \leq \frac{1}{\mathbb{E}[X]} + \frac{\Delta^*}{\mathbb{E}[X]} \to 0$$

Следовательно, $\mathbb{P}(X = 0) \to 0$, и функция $r(n) = 1/n$ строго доказана в качестве пороговой для свойства «содержать подграф $K_3$».

Обобщение: плотность подграфов и сбалансированность

Возникает фундаментальный вопрос: верно ли, что для произвольного графа $H$ с $v_H$ вершинами и $e_H$ рёбрами порог появления всегда равен $n^{-v_H / e_H}$ (точке, где $\mathbb{E}[X] = \Theta(n^{v_H} p^{e_H}) \approx 1$)?

Ответ отрицателен, и причина кроется в локальных скоплениях рёбер внутри подструктур.

Пусть, например, граф $H$ состоит из клики $K_4$, к одной из вершин которой присоединён висячий край. У такого графа $v_H = 5$ вершин и $e_H = 7$ рёбер. Точка $\mathbb{E}[X] \approx 1$ даёт наивный порог $p = n^{-5/7} \approx n^{-0.714}$. Если задать вероятность $p = n^{-0.7}$, среднее число копий всего графа уходит в бесконечность: $\mathbb{E}[X] = \Theta(n^5 (n^{-0.7})^7) = \Theta(n^{0.1}) \to \infty$. Однако математическое ожидание числа 4-клик $K_4$ равно $\Theta(n^4 (n^{-0.7})^6) = \Theta(n^{-0.2}) \to 0$. Клики $K_4$ в графе отсутствуют a.a.s., а значит, не может появиться и вся конструкция $H$.

Препятствием к глобальному появлению графа служат его наиболее плотные подграфы.

Определение максимальной плотности подграфа: Для непустого графа $H$ плотностью называется отношение $d(H) = \frac{e_H}{v_H}$. Максимальная плотность подграфов определяется как:

$$m(H) = \max_{H' \subseteq H, \, v_{H'} > 0} \frac{e_{H'}}{v_{H'}}$$

Граф $H$ называется сбалансированным, если $m(H) = \frac{e_H}{v_H}$, то есть ни один его собственный подграф не превосходит сам граф по плотности.

Теорема Боллобаша (1981)

Для любого фиксированного графа $H$, содержащего хотя бы одно ребро, пороговой функцией появления изоморфной копии $H$ в случайном графе $G(n, p)$ является:

$$r(n) = n^{-1/m(H)}$$

Если граф сбалансирован (например, полный граф $K_k$, цикл $C_k$ или полный двудольный граф с равными долями $K_{r, r}$), то $m(H) = e_H / v_H$, и порог определяется непосредственно по глобальному математическому ожиданию: $r(n) = n^{-v_H / e_H}$. Для несбалансированных графов именно плотнейшая часть выступает «бутылочным горлышком», определяющим фазовый переход всей конструкции.

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