# MIT: «Порог 1/n определяет появление треугольников в случайных графах»

Источник: https://www.youtube.com/watch?v=a4md4P4Mu_U
Канал: MIT OpenCourseWare
Опубликовано: 06.11.2024

---

В области вероятностной комбинаторики одной из фундаментальных задач является изучение свойств случайных структур. В лекции от **MIT OpenCourseWare** подробно рассматривается классическая модель случайного графа и выводится точный порог (threshold), при котором в графе с высокой вероятностью начинают появляться треугольники.

## 📈 Модель случайного графа Эрдеша — Реньи (GNP)
[[JUMP:00:39]]

Объектом исследования выступает модель случайного графа, известная как **GNP**. Эта математическая структура строится следующим образом:

*   **Вершины:** В графе фиксируется $n$ вершин [0:46].
*   **Ребра:** Для каждой возможной пары вершин ребро между ними проводится независимо с вероятностью $P$ [0:53].
*   **Процесс:** По сути, для каждого потенциального ребра подбрасывается «смещенная монета» (biased coin), которая выпадает «орлом» с вероятностью $P$. Если выпал орел — ребро добавляется в граф [1:05].

Основной вопрос лекции: при каких значениях $P$ этот случайный объект «типично» (с вероятностью, стремящейся к единице при росте $n$) содержит треугольник? В данных рассуждениях $P$ рассматривается как функция от $n$, что позволяет анализировать асимптотическое поведение графа [1:33].

## 🔍 Теорема о пороге появления треугольника
[[JUMP:02:11]]

Центральным утверждением лекции является доказательство того, что значение **$1/n$** является критическим порогом для свойства содержать треугольник [4:11]. Математически это разделяется на два утверждения:

1.  **Теорема 0 (Zero Statement):** Если произведение $n \cdot P$ стремится к 0 (то есть $P$ много меньше $1/n$), то вероятность наличия хотя бы одного треугольника в графе стремится к нулю. Граф типично является «свободным от треугольников» [2:25].
2.  **Теорема 1 (One Statement):** Если $n \cdot P$ стремится к бесконечности (то есть $P$ много больше $1/n$), то граф типично содержит хотя бы один треугольник [3:32].

Лектор подчеркивает, что такие пороговые эффекты — «хлеб с маслом» вероятностной комбинаторики, позволяющие понять резкие фазовые переходы в случайных системах [5:05].

## 📉 Доказательство Теоремы 0: Метод первого момента
[[JUMP:05:26]]

Для доказательства отсутствия треугольников при малых $P$ используется **неравенство Маркова**.

*   Пусть случайная величина $X$ — это общее количество треугольников в графе [5:41].
*   Математическое ожидание $E[X]$ вычисляется через линейность ожидания: всего существует $\binom{n}{3}$ троек вершин, и каждая образует треугольник с вероятностью $P^3$.
*   Следовательно, $E[X] \approx n^3 \cdot P^3 = (nP)^3$ [6:08].
*   Если $nP \to 0$, то и ожидаемое количество треугольников стремится к нулю.

Согласно неравенству Маркова, вероятность того, что $X \ge 1$, не превышает математического ожидания $E[X]$. Поскольку ожидаемое число треугольников ничтожно мало, вероятность встретить хотя бы один из них также исчезающе мала при больших $n$ [7:07].

## 📊 Доказательство Теоремы 1: Метод второго момента
[[JUMP:08:12]]

Вторая часть задачи сложнее. Тот факт, что ожидаемое число треугольников $E[X]$ стремится к бесконечности, еще не гарантирует, что треугольник найдется в «типичном» графе. Теоретически $X$ может быть равно нулю в 99% случаев и быть экстремально большим в оставшемся 1%, что даст высокую среднюю величину [8:55].

Для исключения такого сценария лектор использует **неравенство Чебышёва** и анализ концентрации величины вокруг среднего значения [9:43].

### Математическая стратегия:
С помощью неравенства Чебышёва выводится следствие: если дисперсия $Var(X)$ много меньше квадрата ожидания $(E[X])^2$, то вероятность того, что $X = 0$, стремится к нулю [12:11]. Это означает, что значение случайной величины «концентрируется» вокруг своего (в данном случае — растущего) среднего значения [12:41].

### Анализ ковариации:
Для расчета дисперсии $X$ (которое представлено как сумма индикаторных переменных для каждой тройки вершин) необходимо проанализировать ковариацию между парами потенциальных треугольников $T$ и $T'$ [16:14]. Рассматриваются три случая:

1.  **Непересекающиеся треугольники:** Если тройки вершин не имеют общих ребер, их появления независимы, и ковариация равна 0 [20:55].
2.  **Общее ребро:** Треугольники имеют две общие вершины. Это дает вклад в дисперсию порядка $n^4 P^5$ [25:06].
3.  **Идентичные треугольники:** Тройки полностью совпадают ($T=T'$). Вклад в дисперсию порядка $n^3 P^3$ [25:20].

При условии, что $nP \to \infty$, суммарный вклад этих членов оказывается пренебрежимо мал по сравнению с $(E[X])^2$. Это доказывает, что при $P \gg 1/n$ случайный граф почти наверняка содержит треугольники [26:18].

## 🎓 Заключение и значение метода
[[JUMP:28:12]]

Продемонстрированная техника является классическим примером вероятностного метода. Лектор резюмирует, что понимание пороговых функций позволяет математикам предсказывать поведение сложных сетей и структур [28:25]. Хотя для треугольников доказательство выглядит относительно простым, аналогичные методы применяются для анализа гораздо более сложных свойств графов, где требуются продвинутые аналитические инструменты [28:39].