Один говорил «очень редко» , другой — «очень часто». 35-летний спор ученых о графах завершился неожиданностью

В конце 1980-х годов на математической конференции в Лозанне два выдающихся ученых — Нога Алон и Питер Сарнак — затеяли спор, который растянулся на десятилетия. Оба математика изучали особые структуры, названные графами-расширителями: сети точек, соединенных линиями. На первый взгляд в них нет ничего примечательного, но их свойства поражают: даже при минимальном количестве соединений между точками такая сеть остается невероятно прочной и устойчивой.

Уникальность графов-расширителей заключается в их способности эффективно передавать сигналы при минимуме затраченных ресурсов. Любая группа точек такой сети имеет множество связей с остальными элементами. Благодаря этому информация быстро распространяется по всей системе, несмотря на общую экономность конструкции. Даже при нарушении части соединений сеть сохраняет работоспособность.

Однако главное внимание математиков привлекли не просто хорошие, а идеальные графы-расширители. В них соотношение между числом связей и скоростью передачи сигналов достигает теоретического предела. Если в обычном графе информация распространяется достаточно быстро, то в идеальном она движется с максимально возможной скоростью, предсказанной математической теорией. При этом сеть остается предельно экономичной: любая дополнительная связь окажется избыточной, а удаление существующей — нарушит идиллию.

Сарнак утверждал, что найти такие графы крайне сложно. Алон же, опираясь на опыт изучения случайных структур, считал, что идеальные графы должны встречаться часто: по его мнению, достаточно соединить точки случайным образом по определенным правилам, и результат с высокой вероятностью окажется идеальным расширителем.

В 1988 году математики Питер Сарнак, Александр Луботцкий и Ральф Филлипс впервые сумели построить идеальные графы-расширители, опираясь на сложные результаты из теории чисел, полученные в начале XX века индийским математиком Сринивасой Рамануджаном . Созданные структуры достигали теоретического максимума связности — границы Алона-Боппаны. В честь индийского гения, чьи идеи сделали это открытие возможным, такие конструкции назвали графами Рамануджана. В том же году Григорий Маргулис предложил альтернативный способ построения идеальных расширителей, используя совершенно другой математический аппарат — методы теории динамических систем.

На первый взгляд логично предположить, что создание безупречной структуры требует колоссальных усилий, — поясняет Рамон ван Хандель из Института перспективных исследований в Принстоне.

Однако в математике нередко происходит обратное: то, что сложно сконструировать целенаправленно, может часто возникать само по себе. Ученый также добавляет:

Такое случается постоянно. Придуманная вручную конструкция может не иметь нужных свойств, а случайно возникшая — обладать ими в полной мере.

На этот принцип и опирался Алон в дискуссии с Сарнаком. Он считал, что сложность построения таких графов отражает лишь несовершенство человеческих методов, а не их истинную редкость.

В 2008 году появилось важное исследование , в котором математики анализировали большие наборы регулярных графов и их собственные значения. Компьютерное моделирование, охватившее миллионы различных структур, показало противоречивую картину: идеальные графы-расширители не были редкостью, но и не составляли большинство. Такой неопределенный результат только усложнил задачу — теперь требовалось найти точный математический метод для подсчета их доли среди всех возможных графов.

Решающий шаг к разгадке сделали физики, но пришел он с неожиданной стороны. В то время как одни математики пытались напрямую решить загадку графов, профессор Гарварда Хонг-Цер Яу занимался совсем другой задачей. Он исследовал поведение случайных матриц — таблиц чисел, которые заполняются по законам случайности, подобно результатам многократного подбрасывания монеты.

В середине XX века физики разработали этот математический аппарат для изучения сложных квантовых систем. В 1955 году Юджин Вигнер впервые применил случайные матрицы для описания энергетических уровней в ядрах тяжелых атомов. Он обнаружил поразительную закономерность: разные способы построения таких матриц приводили к одинаковым статистическим распределениям. Вне зависимости от того, заполнялась ли таблица целыми или дробными числами, положительными или отрицательными — определенные характеристики всегда подчинялись единому математическому закону.

Феномен, казавшийся сначала чисто физическим, неожиданно оказался связан с теорией графов. Ведь любую сеть точек и связей между ними можно представить в виде таблицы из нулей и единиц.

Вигнер предположил, что подобная закономерность должна проявляться для любых случайных матриц. Многие сочли идею фантастической. "Коллеги не верили его словам", — вспоминает Яу.

В 2013 году Сарнак предложил Яу применить гипотезу универсальности к задаче о графах-расширителях. Если бы числовые характеристики случайных графов подчинялись закономерности Вигнера, можно было бы вычислить вероятность появления идеальных структур.

К 2015 году международная группа во главе с Яу разработала принципиально новый подход к решению проблемы. План предполагал три сложных этапа. На первом этапе ученые намеревались применить особую технику "возмущений" — внести в матрицы графов минимальные случайные изменения, не нарушающие их базовую структуру. Второй этап требовал доказать, что видоизмененные матрицы следуют закономерностям Вигнера. Заключительная часть работы должна была подтвердить, что внесенные изменения настолько незначительны, что не влияют на ключевые свойства исходных графов.

После пяти лет интенсивной работы и защиты диссертации Цзяоян Хуана команда достигла первого серьезного успеха. Математики сумели доказать, что гипотеза Вигнера верна для графов с большим количеством связей. Однако для полного решения исторической загадки требовалось расширить доказательство на все возможные типы регулярных графов.

Прорыв наступил осенью 2022 года с приходом в команду Тео Маккензи . Молодой математик, по словам его научного руководителя Никхила Шриваставы, обладал редким даром — способностью находить нестандартные подходы к сложнейшим задачам. Свежий взгляд Маккензи и его тщательный анализ предыдущих результатов открыли новые перспективы в исследовании. "Именно коллективная работа и разные точки зрения помогают увидеть скрытые закономерности", — подчеркивает Яу.

Первоначально группа получила лишь приближенный результат. Математики не могли с абсолютной точностью рассчитать распределение характеристик видоизмененных матриц. Тем не менее, они обнаружили важные закономерности, косвенно подтверждающие их гипотезу.

Ключ к окончательному решению нашелся в параллельном исследовании Хуана. Он изучал особые математические соотношения — петлевые уравнения, описывающие поведение чисел в случайных матрицах. Ученый понял: если их модель удовлетворяет этим уравнениям с высокой точностью, это даст недостающее звено для завершения доказательства.

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

Спустя 35 лет спор Сарнака и Алона наконец получил неожиданное разрешение. Несколько месяцев назад, в декабре, вышла научная статья с окончательными выводами. Среди всех регулярных графов примерно 69% оказались идеальными расширителями — не редкость, но и не подавляющее большинство.

Открытие показало, что гипотеза универсальности охватывает гораздо более широкий круг явлений, чем предполагали ученые. Исследователи планируют использовать разработанные методы для решения других математических задач, связанных со случайными структурами.

В каком-то смысле ошиблись мы оба, — признает Алон. — Хотя, — добавляет он с улыбкой, — моя догадка была чуть ближе к истине, ведь вероятность оказалась больше половины.

Это исследование не только поставило точку в давнем математическом споре, но и продемонстрировало удивительную связь между разными областями науки. Физическая интуиция гения, изучавшего атомные ядра, помогла разгадать загадку абстрактных математических структур. А методы, разработанные в ходе решения, открывают новые перспективы для понимания случайных процессов в самых разных областях — от квантовой механики до теории информации.