Натали Бихейг, Даниэл Илькович и Ричард Монтгомери решили задачу, висевшую в математике более 20 лет. Они построили точное соотношение между двумя центральными классами случайных графов: регулярными и биномиальными. Оказалось, что регулярный граф с высокой вероятностью находится строго между двумя биномиальными графами близкой плотности. Такая конструкция работает как универсальный мост — известные теоремы о биномиальных графах теперь автоматически применяются к регулярным графам, вместо того чтобы доказывать каждую заново.

Работу опубликовали как препринт в октябре 2025 года. Чон Хан Ким и Ван Ха Ву сформулировали гипотезу ещё в 2004-м.

Граф состоит из вершин и рёбер. Такой формализм охватывает компьютерные сети, социальные контакты, биологические системы — любые структуры связей. В биномиальной модели G(n,p) каждая пара вершин получает ребро независимо с вероятностью p. Независимость сильно упрощает расчёты, и за десятилетия накопился огромный запас результатов для таких графов.

С d-регулярными графами труднее. Каждая вершина должна иметь ровно d соседей, поэтому добавление одного ребра ограничивает возможности остальных. Независимость теряется, методы биномиальных моделей перестают работать прямо.

Ким и Ву предположили: при d, растущем быстрее log n, случайный d-регулярный граф можно вложить между двумя биномиальными графами вероятности d/n. Нижний лежит полностью внутри регулярного, регулярный — полностью внутри верхнего.

Логика «сэндвича» простая. Если нижний биномиальный граф имеет свойство, которое сохраняется при добавлении рёбер, то и содержащий его регулярный граф это свойство наследует. Верхний граф позволяет обратное: если регулярный граф имеет свойство, исчезающее при удалении рёбер, то и верхний биномиальный граф его имеет. Один результат о связи моделей заменяет множество отдельных доказательств.

Сложность была не в самих трёх графах. Требовалось связать случайные процессы так, чтобы распределения остались корректными и одновременно обеспечилось вложение. Бихейг, Илькович и Монтгомери развили подход, основанный на методе Пу Гао, Михаила Исаева и Брендана Маккея.

Для нижней половины исследователи строят биномиальный и регулярный графы параллельно, добавляя рёбра пошагово. Если ребро появляется в биномиальной модели, его добавляют и в регулярный. Если нет, специальная адаптивная вероятность решает, нужно ли его регулярному графу для финального баланса степеней вершин.

Верхнюю половину строят зеркально: начинают с полного графа и удаляют рёбра, пока регулярный не окажется внутри биномиального. Метод покрыл весь диапазон d ≫ log n из исходной гипотезы.

Раньше математики добывали отдельные куски результата. Гао, Исаев и Маккей получили полный «сэндвич» для плотных графов, позже границу сдвинули до d ≫ log4 n. На этом уровне уже можно было переносить теоремы о гамильтоновых циклах, хроматическом числе, диаметре и фазовых переходах, но полный диапазон оставался недостижим.

Новая работа закрыла разрыв полностью. Математик Гил Калаи назвал результат «метатеоремой»: ценность в том, что вся библиотека знаний о биномиальных графах становится инструментом для регулярных графов, длинные доказательства сокращаются до нескольких строк.

Практически это не означает, что появился волшебный алгоритм для интернета или соцсетей. Результат принадлежит вероятностной комбинаторике. Но случайные графы служат базовыми моделями для анализа крупных сетей, поэтому более крепкая связь между двумя фундаментальными моделями даёт универсальный инструмент для систем с жёстко ограниченной степенью вершин.