# Математика случайности: как Пауль Эрдёш доказал существование контринтуитивных графов Источник: https://www.youtube.com/watch?v=16Vhe_1b974 Канал: MIT OpenCourseWare Опубликовано: 06.11.2024 --- В мире математики существуют вопросы, ответы на которые кажутся интуитивно понятными, но на деле оказываются ложными. Один из таких классических вопросов касается связи между локальной структурой графа и его глобальными свойствами: может ли граф, который вблизи каждой вершины выглядит простым и разреженным (как дерево), требовать для своей раскраски огромного количества цветов? В лекции от **MIT OpenCourseWare** разбирается знаменитая теорема Пауля Эрдёша, которая с помощью вероятностного метода доказывает существование таких контринтуитивных объектов. ## 🧭 Понятия обхвата и хроматического числа [[JUMP:00:12]] Прежде чем переходить к доказательству, необходимо зафиксировать два фундаментальных определения теории графов [0:25]: * **Хроматическое число ($\chi(G)$):** минимальное количество цветов, необходимое для раскраски вершин графа так, чтобы никакие две соседние вершины не имели одинаковый цвет [0:39]. * **Обхват (Girth):** длина самого короткого цикла в графе [0:44]. Если в графе вообще нет циклов (дерево), его обхват считается бесконечным [1:22]. В качестве примеров приводятся графы с обхватом 4 (где кратчайший цикл — квадрат) и обхватом 3 (где есть хотя бы один треугольник) [0:55]. В математическом сообществе долгое время существовала гипотеза: если графу требуется много цветов для раскраски (высокое хроматическое число), то в нём обязательно должны быть плотные локальные структуры, такие как «клики» (полные подграфы) или хотя бы короткие циклы [1:50]. Логика проста: если мы знаем, что в графе есть клика из $K$ вершин, нам точно нужно не менее $K$ цветов [2:03]. Однако теорема Эрдёша полностью опровергает идею о том, что высокое хроматическое число дает какую-либо локальную информацию о графе [2:53]. ## 📜 Теорема Эрдёша: удивительный результат 1950-х [[JUMP:03:09]] В 1950-х годах венгерский математик Пауль Эрдёш сформулировал и доказал теорему, ставшую классикой комбинаторики: для любых целых положительных чисел $K$ и $L$ существует граф, обхват которого больше $L$, а хроматическое число — больше $K$ [3:42]. Это означает, что можно построить граф, который: 1. **Локально выглядит как дерево:** если «прогуляться» от любой вершины на расстояние $L$, вы не обнаружите ни одного цикла [4:10]. 2. **Глобально крайне сложен:** несмотря на локальную пустоту, раскрасить его менее чем в $K$ цветов невозможно [4:22]. До Эрдёша математики пытались строить такие графы вручную, используя сложные явные конструкции («ручной метод»), но не могли добиться произвольно больших значений обхвата и хроматического числа одновременно [5:14]. Эрдёш совершил прорыв, применив **вероятностный метод**. Вместо того чтобы строить конкретный пример, он показал, что если взять случайный граф и немного его подправить, то искомый объект найдется с ненулевой вероятностью [5:45]. ## 🎲 Метод модификации случайного графа [[JUMP:06:03]] Доказательство строится на модели случайного графа Эрдёша — Реньи ($G_{n,p}$), где для каждой пары из $n$ вершин ребро проводится независимо с вероятностью $p$ [6:22]. ### Шаг 1: Подсчет коротких циклов Спикер вводит случайную величину $X$, равную количеству циклов длиной не более $L$ [7:33]. Используя линейность математического ожидания, вычисляется ожидаемое количество таких циклов. При выборе вероятности $p = n^{\theta-1}$ (в видео используется специфическое значение через логарифмы для наглядности) оказывается, что ожидаемое число коротких циклов растет гораздо медленнее, чем число вершин $n$ [11:18]. По неравенству Маркова вероятность того, что коротких циклов будет слишком много (больше $n/2$), стремится к нулю при росте $n$ [12:12]. Это означает, что в типичном случайном графе "дефектов" в виде коротких циклов относительно мало. ### Шаг 2: Хроматическое число и число независимости Связать хроматическое число со случайным графом напрямую сложно, поэтому используется связь с **числом независимости** ($\alpha(G)$) — размером самого большого подмножества вершин, между которыми нет ребер [14:26]. Существует жесткая зависимость: хроматическое число всегда не меньше, чем общее количество вершин, деленное на число независимости ($\chi(G) \geq n / \alpha(G)$) [14:58]. Математические расчеты показывают: * При определенном выборе параметров вероятность того, что в графе найдется независимое множество большого размера $H$, исчезающе мала [17:55]. * Следовательно, в типичном случайном графе число независимости мало, а значит, хроматическое число — велико [18:10]. ## 🛠 Метод «альтерации» (исправления дефектов) [[JUMP:19:06]] Финальный этап доказательства — это демонстрация того, что мы можем одновременно удовлетворить обоим условиям. При достаточно большом $n$ существует граф $G$, в котором одновременно мало коротких циклов и нет больших независимых множеств [20:03]. Чтобы получить искомый граф $G'$, применяется «метод альтерации»: 1. Из каждой «короткой» петли (длиной $\leq L$) удаляется по одной вершине [21:00]. 2. В результате все короткие циклы исчезают — теперь обхват графа гарантированно больше $L$ [21:29]. 3. Поскольку удалено не более $n/2$ вершин (их было мало), в графе остается еще как минимум $n/2$ вершин [22:07]. 4. Число независимости при удалении вершин не может вырасти, а значит, оно остается малым. 5. Итоговое хроматическое число нового графа $G'$ оказывается пропорциональным $\log n$ [22:48]. При увеличении $n$ это значение может стать больше любого наперед заданного числа $K$ [23:03]. Таким образом, существование графа с высоким обхватом и высоким хроматическим числом доказано. Этот результат остается одним из самых красивых и элегантных примеров того, как введение случайности помогает решать чисто детерминированные задачи теории графов [24:44].