Краткий ответ (основной результат)
- Порог связности в модели $G(n,p)$ равен $p(n)\sim \frac{\ln n}{n}$. Более точно:
- Если $p=\frac{\ln n+\omega (1)}{n}$ (т.е. $\omega (1)\to \infty$), то $G(n,p)$ с высокой вероятностью (whp) связен.
- Если $p=\frac{\ln n-\omega (1)}{n}$, то whp граф несвязан (обычно есть изолированные вершины).
- Для сдвига на константу: при $p=\frac{\ln n+c}{n}$ вероятность связности имеет предельное значение
$$\mathrm{Pr}(G(n,p)\text{связан})\to e^{-e^{-c}}.$$
Основные методы доказательства и идеи (коротко)
1. Ожидание числа изолированных вершин (первая оценка / первый момент).
- Обозначим $X_1$ — число изолированных вершин. Тогда
$$\mathbb{E}{X}_1=n(1-p{)}^{n-1}\approx n{e}^{-p(n-1)}.$$ - Если $p=\frac{\ln n-\omega (1)}{n}$, то $\mathbb{E}{X}_1\to \infty$ и по первой оценке (или по трюку Маркова) whp есть изолированные вершины → несвязность.
- Если $p=\frac{\ln n+\omega (1)}{n}$, то $\mathbb{E}{X}_1\to 0$; с дополнительными концентрационными аргументами это даёт отсутствие изолированных вершин whp.
2. Появление пуассоновского предела (метод моментов / Stein–Chen).
- При $p=\frac{\ln n+c}{n}$ число изолированных вершин сходится по закону к пуассоновской величине с параметром $\lambda =e^{-c}$. Следовательно
$$\mathrm{Pr}(X_1=0)\to e^{-\lambda }=e^{-e^{-c}}.$$ - Это даёт точный переход для отсутствия изолированных вершин; далее нужно показать, что другие виды малых компонент не влияют на вероятность связности в этом окне.
3. Подсчёт малых компонент (ожидание числа компонент размера $k$).
- Ожидаемое число компонент размера $k$ оценивают через выбор множества из $k$ вершин и вероятность, что они образуют связную компоненту без рёбер наружу. Для деревьев используют число Кэли $k^{k-2}$:
$$\mathbb{E}[N_k]\le \left(\genfrac{}{}{0ex}{}{n}{k}\right)k^{k-2}{p}^{k-1}(1-p{)}^{k(n-k)}.$$ - Суммирование по малым $k$ показывает: при $p$ выше порога суммарный вклад компонент размера $\ge 2$ мал; значит отсутствие изолированных вершин обеспечивает связность.
4. Исследование процесса исследования (BFS) и приближение ветвящимся процессом.
- Компоненту, начинающуюся из вершины, моделируют галтон‑ватсоновским процессом с камерой потомков $\mathrm{Bin}(n,p)$ (приближённо $\mathrm{Poisson}(np)$ при малых $p$).
- Это даёт контроль над размерами компонент (появление гигантской компоненты при $np>1$ и только малые компоненты при $np<1$). Метод особенно полезен в окне $p=O(1/n)$.
5. Техника «sprinkling» (двухэтапное раскрытие).
- Делят $p$ на $p_1+p_2-p_1{p}_2$. Сначала строят $G(n,p_1)$ (получают гигант/мелкие компоненты), затем «подкидывают» остаточные ребра $p_2$, чтобы с большой вероятностью соединить оставшиеся компоненты. Часто используется для доказательства, что выше порога отдельные крупные компоненты с высокой вероятностью связаны дополнительными ребрами.
- Требует независимости появлений рёбер (поэтому хорошо работает в $G(n,p)$).
6. Концентрационные неравенства (Chernoff, Azuma) и убедительные оценки степеней.
- Применяются для контроля степеней вершин, числа рёбер между партиями вершин и т.п. Помогают превратить оценки ожиданий в утверждения whp.
7. Теоремы о резком пороге (Friedgut–Kalai) дают общие результаты о ширине перехода свойства связности, но для точных констант требуются более тонкие подсчёты.
Границы применимости методов и ограничения
- Первое‑моментные методы и простые биномиальные оценки легко показывают несвязность ниже порога и отсутствие изолированных вершин выше, но сами по себе не доказывают полную связность без дополнений (нужен контроль остальных компонент).
- Пуассоновская аппроксимация (метод моментов или Stein–Chen) применима, когда зависимости между индикаторными событиями (напр., вершины изолированы) слабые — это так в окне $p\sim \frac{\ln n+c}{n}$. Для более плотных графов она не уместна.
- При $p$ значительно больше $\frac{\ln n}{n}$ многие приближения ветвящимся процессом теряют смысл (т.к. np не мал), но в этом региме связность обычно следует простыми оценками степеней или концентрациями.
- Техника sprinkling специфична для моделей с независимыми рёбрами (G(n,p)); в моделях с зависимостями (например, случайные регулярные графы, геометрические графы) её применение требует модификаций.
- Подсчёт маленьких компонент через комбинаторные оценки становится громоздким при попытке получить сверхточные асимптотики для более сложных свойств; тогда нужны более тонкие инструменты (уточнённые оценки факториальных моментов, аналитические методы).
Короткое резюме
- Порог: $p\sim \frac{\ln n}{n}$. Сильный критерий: $p=\frac{\ln n\pm \omega (1)}{n}$.
- Точные вероятности в окне $p=\frac{\ln n+c}{n}$ связаны с пуассоновским числом изолированных вершин: предельная вероятность связности $e^{-e^{-c}}$.
- Основные методы: первый/второй моменты, пуассоновская аппроксимация (Stein–Chen / метод моментов), ветвящиеся процессы (BFS), подсчёт малых компонент (Cayley для деревьев), sprinkling, концентрационные неравенства. Каждый метод имеет область применимости и свои ограничения, особенно при переходе к иным моделям случайных графов или к другим масштабам $p$.