Крупный план показывает точку «плавления» бесконечного графа | Журнал Кванта

В 2008 году математик Одед Шрамм погиб в результате несчастного случая во время похода в Каскадные горы примерно в 50 милях к востоку от Сиэтла. Хотя ему было всего 46 лет, он создал совершенно новые области математики.

«Он был фантастическим математиком», — сказал Итай Бенджамини, математик из Института науки Вейцмана, друг и соратник Шрамма. «Чрезвычайно креативно, чрезвычайно элегантно, чрезвычайно оригинально».

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

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

В препринт опубликован в октябре, Том Хатчкрофт Калифорнийского технологического института и его докторант Филип Исо доказал гипотезу локальности Шрамма. Их доказательство основано на основных идеях теории вероятностей и других областей математики, которые они умело объединили.

«Это замечательный документ. Это результат долгой работы», — сказал Бенджамини.

Бесконечные кластеры

Слово «перколяция» первоначально относилось к движению жидкости через пористую среду, например, к воде, текущей через кофейную гущу, или нефти, просачивающейся через трещины в скале.

В 1957 году математики Саймон Ральф Бродбент и Джон Майкл Хаммерсли разработали математическую модель этого физического процесса. Спустя десятилетия эта модель стала самостоятельным объектом изучения. Математики изучают перколяцию, потому что она обеспечивает важный баланс: установка проста, но демонстрирует сложные и загадочные особенности.

«Это своего рода каноническая модель для математиков», — сказал Хатчкрофт. «Вы можете думать о вещах визуально. Поэтому с нами очень приятно работать».

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

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

В 2009 году Бенджамини Асаф Нахмиас и Юваль Перес доказанный Гипотеза локальности Шрамма, как она теперь известна, относится к определенному типу транзитивного графа, напоминающего дерево. Шрамм, однако, постулировал, что это справедливо для всех транзитивных графов (за исключением одномерных графов).

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

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

Транзитивные графы могут принимать множество форм. Это может быть простая сетка, состоящая из квадратов, треугольников, шестиугольников или какой-либо другой формы. Или они могут сформировать более сложный объект, например «3-регулярное дерево», где одна центральная точка соединяется с тремя вершинами, а каждая вершина затем разветвляется, создавая две новые до бесконечности, первые несколько шагов которого можно увидеть здесь:

Разнообразие транзитивных графов затрудняло доказательство гипотезы Шрамма о локальности. За 15 лет между гипотезой Шрамма и доказательством Исо и Хатчкрофта различные группы математиков доказали гипотезу для конкретных типов графов, но их идеи так и не распространились на общий случай.

«Пространство всех возможных геометрических форм огромно, и в нем всегда скрываются странные вещи», — сказал Хатчкрофт.

Расширение объектива

Исо и Хатчкрофт изначально не искали решение гипотезы локальности Шрамма, которая применима к бесконечным графам. Вместо этого они изучали перколяцию на конечных графах. Но у них возникла идея, которая внезапно переключила их внимание на эту гипотезу.

«Мы придумали этот новый инструмент и подумали: о, похоже, это может быть полезно для атаки на локальность», — сказал Исо.

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

Они полагались на технику, которую можно назвать «расширением линзы». Начните с одной вершины. Затем уменьшите масштаб, чтобы просмотреть все вершины, находящиеся на расстоянии всего одного ребра исходного графа. На квадратной сетке теперь вы сможете увидеть всего пять вершин. Снова расширьте линзу, чтобы увидеть все вершины на расстоянии двух ребер, а затем на расстоянии трех ребер, четырех ребер и так далее.

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

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

Для квадратной сетки количество вершин растет относительно медленно. Это примерно ширина вашей линзы в квадрате. После 10 шагов вы найдете около 100 вершин. Но 3-регулярное дерево растет экспоненциально быстрее — примерно в 2 степени ширины линзы. После 10 шагов вы увидите примерно 1,024 вершины. На иллюстрации ниже показано, как 3-регулярное дерево становится намного больше всего за семь шагов, хотя поначалу квадратная сетка имеет больше вершин. В общем, графики могут иметь разные темпы роста в разных масштабах — они могут начинаться быстро, а затем замедляться.

Еще в 2018 году Хатчкрофт использовал похожую идею доказать гипотезу локальности для быстрорастущих графов, таких как 3-регулярное дерево. Но это не работало для медленнорастущих графов, таких как квадратная сетка, или для графов, которые растут со средней скоростью и не соответствуют ни математическим критериям быстрого роста, ни критериям медленного роста.

«Именно здесь ситуация становится действительно неприятной в течение примерно трех лет», — сказал Хатчкрофт.

Структура против расширения

Для графиков, на которых представлены темпы роста в разных масштабах, вам придется использовать различные методы.

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

В 2021 году Себастьян Мартино из Университета Сорбонны в Париже, работающий с Даниэлем Контрерасом и Винсент Тассион ETH Zurich, смог использовать это свойство для доказать гипотезу локальности Шрамма для графов, которые со временем растут медленно.

К этому моменту две группы математиков успешно рассмотрели эту гипотезу с разных сторон: быстрого и медленного роста. Но это оставило значительные пробелы. Во-первых, существует категория промежуточного роста, которая не была охвачена техникой Исо и Хатчкрофта или доказательством Контрераса, Мартино и Тассиона. Другая проблема заключалась в том, что эти аргументы по-прежнему не применимы к графикам с изменяющимися темпами роста — только к тем, которые остаются быстрыми или медленными. Чтобы аргумент Контрераса, Мартино и Тассиона можно было применить к произвольным графикам, недостаточно того, чтобы геометрия в конечном итоге выглядела скучной при уменьшении масштаба, объяснил Исо: «Нам нужно, чтобы она выглядела скучно сейчас, вблизи текущего масштаба».

Середина ниоткуда

Транзитивные графы промежуточного роста очень загадочны. Математикам никогда не приходилось находить пример транзитивного графа, рост которого попадал бы в этот диапазон. Вполне возможно, что их даже не существует. Но математики не доказали их несуществование, поэтому любое полное доказательство гипотезы о локальности Шрамма должно касаться их. Еще больше усугубляла проблему Исо и Хатчкрофт, нуждавшаяся в рассмотрении графиков, которые могли лишь кратковременно иметь промежуточный рост в определенном масштабе длины, даже если они росли быстрее или медленнее при увеличении или уменьшении масштаба.

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

Во-первых, они модифицировали технику 2018 года, которую Хатчкрофт применил к быстрорастущим графикам, для работы с графиками, которые меняют уровни роста в разных масштабах. Затем они рассмотрели случай медленного роста, в 27-страничная статья в августе они поделились подробной информацией о работе над Контрерасом, Мартино и Тассионом. Наконец, в своем октябрьском препринте они разработали еще один аргумент, используя теорию случайных блужданий — линий, которые беспорядочно колеблются в пространстве — для рассмотрения случая промежуточного роста. Завершив трихотомию, они доказали гипотезу Шрамма о локальности.

«Нам пришлось использовать все, что мы знали, для решения этой проблемы», — сказал Хатчкрофт.

Решение дает математикам лучшее понимание того, что происходит выше порога перколяции, где вероятность появления бесконечного кластера составляет 100%, и ниже него, где вероятность равна 0%. Но математики до сих пор озадачены тем, что происходит именно на пороге для большинства графиков, включая трехмерную сетку. «Это, наверное, самый известный и самый основной открытый вопрос в теории перколяции», — сказал Рассел Лайонс Университета Индианы.

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

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

Исправление: 18 декабря 2023
Число узлов внутри n звеньев начального узла 3-регулярного графа возрастает примерно на 2ⁿ, а не 3ⁿ как изначально говорилось в этой статье. Статья исправлена.

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