Эрдёш и Реньи: случайный граф и фазовый переход

Вероятностный метод

Приём, который Пал Эрдёш ввёл в 1947 году и который стал одним из главных инструментов современной комбинаторики.

Задача. Числа Рамсея: $R(k,k)$ — наименьшее $n$ такое, что при любой раскраске рёбер полного графа на $n$ вершинах в два цвета найдётся одноцветный полный подграф на $k$ вершинах. Нужна нижняя оценка: раскраска без одноцветной клики.

Рассуждение Эрдёша (1947), три строки. Раскрасим каждое ребро $K_n$ независимо и равновероятно. Для фиксированного набора из $k$ вершин вероятность, что все $C_{k}^{2}$ рёбер между ними одного цвета, равна $2\cdot 2^{-C_{k}^{2}}$. Наборов всего $C_{n}^{k}$, поэтому

$$P(\exists\ \text{одноцветная } k\text{-клика}) \leqslant C_{n}^{k}\cdot 2^{1-C_{k}^{2}}.$$

Если правая часть меньше единицы, то с положительной вероятностью одноцветной клики нет, — значит, хотя бы одна такая раскраска существует. Подставляя $C_n^k \leqslant n^k/k!$, получаем условие, дающее

$$R(k,k) > 2^{k/2} \quad\text{(при } k\geqslant3).$$

Ни одна конкретная раскраска не предъявлена. Более того: явных конструкций, дающих экспоненциальную нижнюю оценку, не найдено до сих пор — за восемьдесят лет. Мы знаем, что хорошие раскраски составляют почти все, и не умеем указать ни одной.

Тот же парадокс, что у Кантора с трансцендентными числами и у Бореля с нормальными числами. Случайность как способ доказательства существования — идея, полностью принадлежащая XX веку.

Модель случайного графа

Серия работ Пала Эрдёша и Альфреда Реньи: «On random graphs I» (1959) и особенно «On the evolution of random graphs» (1960), в трудах Математического института Венгерской академии наук.

Модель $G(n,p)$. Берём $n$ вершин; каждое из $C_{n}^{2}$ возможных рёбер проводим независимо с вероятностью $p$.

(Родственная модель $G(n,m)$ — равномерный выбор среди графов с ровно $m$ рёбрами; при $m\approx pC_n^2$ они асимптотически эквивалентны. Заметим, что модель $G(n,m)$ независимо рассматривал Эдгар Гилберт, отсюда встречающееся название «модель Эрдёша — Реньи — Гилберта».)

Вопрос: как свойства графа зависят от $p$?

Пороговые явления

Главное открытие: свойства графа возникают не постепенно, а скачком. Существует пороговая функция $p^{*}(n)$ такая, что при $p \ll p^{*}$ свойство почти наверняка отсутствует, при $p\gg p^{*}$ — почти наверняка присутствует.

Свойство	Порог
Появление гигантской компоненты	$p = 1/n$
Исчезновение изолированных вершин, связность	$p = \dfrac{\ln n}{n}$
Появление треугольников	$p = 1/n$
Гамильтонов цикл	$p = \dfrac{\ln n + \ln\ln n}{n}$

Фазовый переход при $p=1/n$

Самый эффектный результат, и его стоит разбирать подробно.

До порога компоненты малы, после — одна из них охватывает заметную долю всех вершинMathLocus · построено для этого сайта

Обозначим $c = pn$ — средняя степень вершины (среднее число соседей). Тогда:

$c<1$: все компоненты связности малы, крупнейшая имеет размер $O(\ln n)$. Граф — россыпь мелких кусков.
$c=1$: критическая точка, крупнейшая компонента имеет размер порядка $n^{2/3}$.
$c>1$: возникает единственная гигантская компонента, содержащая долю $\beta$ всех вершин, где $\beta$ — единственный положительный корень уравнения

$$\beta = 1 - e^{-c\beta}.$$

Все остальные компоненты остаются размера $O(\ln n)$.

Пример. При $c=1{,}5$ решение $\beta\approx0{,}583$: гигантская компонента охватывает 58% вершин. При $c=2$: $\beta\approx0{,}797$. При $c=3$: $\beta\approx0{,}941$.

Откуда уравнение. Здесь замечательная связь с ветвящимися процессами (см. точку о Гальтоне и Ватсоне). Обход графа от случайной вершины «в ширину» ведёт себя как ветвящийся процесс с числом потомков $\mathrm{Poisson}(c)$. Вероятность вымирания $\eta$ такого процесса удовлетворяет $\eta = f(\eta)$, где $f(s)=e^{-c(1-s)}$ — производящая функция пуассоновского распределения. Подставляя $\beta = 1-\eta$, получаем в точности $\beta = 1-e^{-c\beta}$. Критичность $c=1$ — это в точности критичность ветвящегося процесса, и порог случайного графа наследуется от порога вымирания фамилий.

Аналогия с физикой. Это буквально фазовый переход: как вода при 0°C, граф качественно меняет структуру при переходе параметра через критическое значение, причём вблизи порога поведение описывается степенными законами с универсальными показателями. Теория перколяции и статистическая физика разрабатывали то же явление независимо; сейчас это одна область.

Порог связности

Второй порог, $p = \ln n / n$, объясняется совсем просто и хорошо работает в классе.

Вероятность, что данная вершина изолирована, равна $(1-p)^{n-1}\approx e^{-pn}$. Ожидаемое число изолированных вершин:

$$E[\text{изолир.}] \approx n\,e^{-pn}.$$

Подставим $p = \dfrac{\ln n + c}{n}$:

$$n\,e^{-\ln n - c} = e^{-c}.$$

Число изолированных вершин стремится к пуассоновскому распределению с параметром $e^{-c}$, и вероятность связности стремится к $e^{-e^{-c}}$. При $c\to+\infty$ она стремится к 1, при $c\to-\infty$ — к 0. Порог найден, и найден точно, вплоть до слагаемого.

Разрыв между $1/n$ (гигантская компонента) и $\ln n/n$ (полная связность) содержателен: сначала возникает большой связный кусок, и только гораздо позже к нему присоединяются последние одиночки.

Значение

Комбинаторика. Вероятностный метод стал стандартным инструментом; книга Алона и Спенсера «The Probabilistic Method» — учебник целой области.
Информатика. Случайные графы — модель для анализа алгоритмов, случайных структур данных, рандомизированных алгоритмов.
Сети. Модель $G(n,p)$ — базовая нулевая гипотеза при изучении реальных сетей. Именно на её фоне видно, что реальные сети не таковы: у них степенное распределение степеней вместо пуассоновского (модель Барабаши — Альберт, 1999) и высокая кластеризация (модель Уоттса — Строгаца, 1998). Значение $G(n,p)$ отчасти именно в том, что она даёт эталон, от которого меряют отклонения.
Эпидемиология. Порог $c=1$ — это порог эпидемии: базовое репродуктивное число $R_0=1$ разделяет затухание и вспышку. Прямое продолжение модели Даниила Бернулли (точка о вариоляции выше).

Люди

Пал Эрдёш в Будапеште, 1992Kmhkmh · CC BY 3.0

Пал Эрдёш (1913–1996) — математик без дома, работы и имущества, объехавший мир с двумя чемоданами, написавший около 1500 статей с 500 с лишним соавторами (отсюда «число Эрдёша»). Своеобразный язык: дети — «эпсилоны», алкоголь — «яд», Бог — «Верховный Фашист», ведущий «Книгу», в которой записаны лучшие доказательства.

Альфред Реньи (1921–1970) — основатель и директор Математического института Венгерской академии наук, ныне носящего его имя. Ему принадлежит определение математика как машины для превращения кофе в теоремы (часто приписываемое Эрдёшу).