Математики закрыли гипотезу Кима и Ву, которая больше 20 лет мешала напрямую связывать два важнейших типа случайных графов. Натали Бихейг, Даниэл Илькович и Ричард Монтгомери построили строгий «сэндвич», в котором сложный случайный регулярный граф с высокой вероятностью оказывается между двумя гораздо лучше изученными биномиальными графами почти той же плотности. Результат позволяет переносить на регулярные графы целые классы уже известных теорем вместо того, чтобы каждый раз доказывать их заново.
Полное доказательство появилось в виде препринта в октябре 2025 года, а 18 сентября 2026 года Quanta опубликовала подробный разбор работы. Авторы решили задачу, которую Чон Хан Ким и Ван Ха Ву сформулировали в 2004 году.
Граф в математике состоит из вершин и соединяющих их рёбер. Такая абстракция позволяет описывать самые разные сети, от связей между компьютерами до социальных контактов. В биномиальной модели G(n,p) каждая возможная пара вершин получает ребро независимо с вероятностью p. Независимость сильно упрощает анализ, поэтому за десятилетия математики накопили огромный набор результатов для таких графов.
С регулярными графами всё сложнее. В d-регулярном графе каждая вершина должна иметь ровно d соседей, поэтому выбор одного ребра влияет на допустимость остальных. Независимость исчезает, а многие методы, хорошо работающие для G(n,p), перестают применяться напрямую.
Ким и Ву предположили, что при d, растущем значительно быстрее log n, случайный d-регулярный граф можно с высокой вероятностью поместить между двумя биномиальными графами. Нижний граф должен полностью входить в регулярный, а регулярный, в свою очередь, полностью входить в верхний. Вероятности появления рёбер у обеих внешних моделей при этом стремятся к d/n.
Смысл «сэндвича» становится понятнее на свойствах, которые сохраняются при добавлении или удалении рёбер. Если нижний биномиальный граф уже обладает свойством, которое не исчезает после добавления рёбер, такое свойство автоматически получает содержащий его регулярный граф. Верхний граф позволяет проводить аналогичные рассуждения в обратную сторону. Поэтому один результат о связи моделей заменяет множество отдельных доказательств.
Главная проблема заключалась не в том, чтобы построить три похожих графа по отдельности. Математикам требовалось связать случайные процессы так, чтобы распределения оставались правильными и одновременно выполнялось вложение одного графа в другой. Бихейг, Илькович и Монтгомери решили задачу, развивая метод, предложенный в более ранней работе Пу Гао, Михаила Исаева и Брендана Маккея.
Для нижней половины «сэндвича» исследователи фактически строят биномиальный и регулярный графы параллельно, добавляя рёбра шаг за шагом. Если очередное ребро появляется в биномиальном графе, его добавляют и в регулярный. Когда ребро в биномиальной модели отсутствует, специальная меняющаяся вероятность определяет, потребуется ли оно регулярному графу, чтобы в конце каждая вершина получила ровно нужное число связей.
Верхнюю половину авторы получают зеркальным способом. Процесс начинается с графов, содержащих все возможные рёбра, после чего связи последовательно удаляются, пока регулярный граф не окажется внутри биномиального. Такой подход позволил доказать требуемое вложение во всём диапазоне d ≫ log n, заявленном исходной гипотезой.
До новой работы математики постепенно отвоёвывали отдельные диапазоны параметров. Гао, Исаев и Маккей получили полноценный «сэндвич» для достаточно плотных регулярных графов, а последующие улучшения довели границу примерно до d ≫ log4 n. Предыдущие методы уже позволяли переносить результаты о гамильтоновых циклах, хроматическом числе, диаметре, независимых множествах и фазовых переходах, но не покрывали весь режим, предсказанный Кимом и Ву.
Новая работа закрывает оставшийся разрыв. Математик Гил Калаи назвал результат «метатеоремой», поскольку ценность доказательства состоит не только в одном решённом вопросе. Связь между двумя моделями превращает большую библиотеку знаний о биномиальных графах в инструмент для исследования регулярных графов, а старые многостраничные аргументы в ряде случаев можно заменить значительно более короткими выводами.
Практический эффект не означает, что инженеры теперь смогут одним новым алгоритмом оптимизировать интернет или социальные сети. Результат относится прежде всего к вероятностной комбинаторике. Но случайные графы служат базовыми моделями при изучении больших сетевых структур, поэтому более тесная связь между двумя фундаментальными моделями даёт математикам универсальный способ анализировать системы, где число связей у узлов жёстко ограничено.
