В мире математики существуют вопросы, ответы на которые кажутся интуитивно понятными, но на деле оказываются ложными. Один из таких классических вопросов касается связи между локальной структурой графа и его глобальными свойствами: может ли граф, который вблизи каждой вершины выглядит простым и разреженным (как дерево), требовать для своей раскраски огромного количества цветов? В лекции от MIT OpenCourseWare разбирается знаменитая теорема Пауля Эрдёша, которая с помощью вероятностного метода доказывает существование таких контринтуитивных объектов.
🧭 Понятия обхвата и хроматического числа 0:12
Прежде чем переходить к доказательству, необходимо зафиксировать два фундаментальных определения теории графов :
- Хроматическое число ($\chi(G)$): минимальное количество цветов, необходимое для раскраски вершин графа так, чтобы никакие две соседние вершины не имели одинаковый цвет .
- Обхват (Girth): длина самого короткого цикла в графе .
Если в графе вообще нет циклов (дерево), его обхват считается бесконечным . В качестве примеров приводятся графы с обхватом 4 (где кратчайший цикл — квадрат) и обхватом 3 (где есть хотя бы один треугольник) .
В математическом сообществе долгое время существовала гипотеза: если графу требуется много цветов для раскраски (высокое хроматическое число), то в нём обязательно должны быть плотные локальные структуры, такие как «клики» (полные подграфы) или хотя бы короткие циклы . Логика проста: если мы знаем, что в графе есть клика из $K$ вершин, нам точно нужно не менее $K$ цветов . Однако теорема Эрдёша полностью опровергает идею о том, что высокое хроматическое число дает какую-либо локальную информацию о графе .
📜 Теорема Эрдёша: удивительный результат 1950-х 3:09
В 1950-х годах венгерский математик Пауль Эрдёш сформулировал и доказал теорему, ставшую классикой комбинаторики: для любых целых положительных чисел $K$ и $L$ существует граф, обхват которого больше $L$, а хроматическое число — больше $K$ .
Это означает, что можно построить граф, который:
- Локально выглядит как дерево: если «прогуляться» от любой вершины на расстояние $L$, вы не обнаружите ни одного цикла .
- Глобально крайне сложен: несмотря на локальную пустоту, раскрасить его менее чем в $K$ цветов невозможно .
До Эрдёша математики пытались строить такие графы вручную, используя сложные явные конструкции («ручной метод»), но не могли добиться произвольно больших значений обхвата и хроматического числа одновременно . Эрдёш совершил прорыв, применив вероятностный метод. Вместо того чтобы строить конкретный пример, он показал, что если взять случайный граф и немного его подправить, то искомый объект найдется с ненулевой вероятностью .
🎲 Метод модификации случайного графа 6:03
Доказательство строится на модели случайного графа Эрдёша — Реньи ($G_{n,p}$), где для каждой пары из $n$ вершин ребро проводится независимо с вероятностью $p$ .
Шаг 1: Подсчет коротких циклов
Спикер вводит случайную величину $X$, равную количеству циклов длиной не более $L$ . Используя линейность математического ожидания, вычисляется ожидаемое количество таких циклов. При выборе вероятности $p = n^{\theta-1}$ (в видео используется специфическое значение через логарифмы для наглядности) оказывается, что ожидаемое число коротких циклов растет гораздо медленнее, чем число вершин $n$ . По неравенству Маркова вероятность того, что коротких циклов будет слишком много (больше $n/2$), стремится к нулю при росте $n$ . Это означает, что в типичном случайном графе "дефектов" в виде коротких циклов относительно мало.
Шаг 2: Хроматическое число и число независимости
Связать хроматическое число со случайным графом напрямую сложно, поэтому используется связь с числом независимости ($\alpha(G)$) — размером самого большого подмножества вершин, между которыми нет ребер . Существует жесткая зависимость: хроматическое число всегда не меньше, чем общее количество вершин, деленное на число независимости ($\chi(G) \geq n / \alpha(G)$) .
Математические расчеты показывают:
- При определенном выборе параметров вероятность того, что в графе найдется независимое множество большого размера $H$, исчезающе мала .
- Следовательно, в типичном случайном графе число независимости мало, а значит, хроматическое число — велико .
🛠 Метод «альтерации» (исправления дефектов) 19:06
Финальный этап доказательства — это демонстрация того, что мы можем одновременно удовлетворить обоим условиям. При достаточно большом $n$ существует граф $G$, в котором одновременно мало коротких циклов и нет больших независимых множеств .
Чтобы получить искомый граф $G'$, применяется «метод альтерации»:
- Из каждой «короткой» петли (длиной $\leq L$) удаляется по одной вершине .
- В результате все короткие циклы исчезают — теперь обхват графа гарантированно больше $L$ .
- Поскольку удалено не более $n/2$ вершин (их было мало), в графе остается еще как минимум $n/2$ вершин .
- Число независимости при удалении вершин не может вырасти, а значит, оно остается малым.
- Итоговое хроматическое число нового графа $G'$ оказывается пропорциональным $\log n$ .
При увеличении $n$ это значение может стать больше любого наперед заданного числа $K$ . Таким образом, существование графа с высоким обхватом и высоким хроматическим числом доказано. Этот результат остается одним из самых красивых и элегантных примеров того, как введение случайности помогает решать чисто детерминированные задачи теории графов .
