Погляд великим планом показує точку «плавлення» нескінченного графа | Журнал Quanta

У 2008 році математик Одед Шрамм загинув у результаті нещасного випадку під час походу в Каскадних горах приблизно в 50 милях на схід від Сіетла. Хоча йому було лише 46 років, він створив абсолютно нові галузі математики.

«Він був фантастичним математиком», — сказав Ітай Бенджаміні, математик з Інституту науки Вейцмана та друг і співробітник Шрамма. «Надзвичайно креативно, надзвичайно елегантно, надзвичайно оригінально».

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

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

В препринт опубліковано в жовтні, Том Хатчкрофт Каліфорнійського технологічного інституту та його докторант Філіп Еасо довів гіпотезу Шрамма про локальність. Їхні докази спираються на основні ідеї з теорії ймовірностей та інших галузей математики, які вони вміло об’єднали.

«Це чудовий документ. Це накопичення тривалої роботи", - сказав Бенджаміні.

Нескінченні кластери

Слово «перколяція» спочатку стосувалося руху рідини через пористе середовище, наприклад, вода, що тече через кавову гущу, або нафта, що просочується через тріщини в скелі.

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

«Це свого роду канонічна модель для математиків», — сказав Гатчкрофт. «Ви можете думати про речі візуально. Тому з ним дуже приємно працювати».

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

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

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

У транзитивному графі всі вершини виглядають подібно. Одним із прикладів є двовимірна сітка. Якщо ви виберете будь-які дві вершини, ви завжди зможете знайти симетрію, яка переміщує одну вершину до іншої.

Цей зв'язок виконується для будь-якого транзитивного графа. Через ці симетрії, якщо ви збільшите масштаб і подивіться на будь-які дві ділянки транзитивного графа однакового розміру, вони виглядатимуть однаково. З цієї причини Шрамм вважав, що перспективи крупним планом достатньо, щоб дозволити математикам обчислити поріг перколяції для всіх транзитивних графів.

Транзитивні графи можуть приймати різні форми. Вони можуть бути простою сіткою, що складається з квадратів, трикутників, шестикутників або іншої форми. Або вони можуть сформувати більш складний об’єкт, як-от «3-правильне дерево», де одна центральна точка з’єднується з трьома вершинами, а кожна вершина потім розгалужується, створюючи дві нові до нескінченності, перші кілька кроків яких видно тут:

Різноманітність транзитивних графів ускладнювало доказ гіпотези Шрамма про локальність. За 15 років між гіпотезою Шрамма та доказом Еасо та Гатчкрофта різні групи математиків довели гіпотезу для конкретних типів графіків, але їхні ідеї ніколи не поширювалися на загальний випадок.

«Простір усіх можливих геометрій просто величезний, і тут завжди ховаються дивні речі», — сказав Гатчкрофт.

Розширення лінзи

Іасо та Хатчкрофт спочатку не шукали рішення гіпотези Шрамма про локальність, яка застосовується до нескінченних графів. Натомість вони вивчали перколяцію на кінцевих графах. Але у них виникла ідея, яка раптом переключила їх увагу на припущення.

«Ми придумали цей новий інструмент і подумали: о, це виглядає як те, що може бути корисним для атаки на місцевість», — сказав Еасо.

Щоб довести припущення, їм потрібно було показати, що мікроскопічна перспектива дає точний знімок порогу перколяції. Коли ви переглядаєте лише частину графіка та спостерігаєте великий зв’язаний кластер, ви можете припустити, що граф має нескінченний кластер і, отже, знаходиться вище порогу перколяції. Еасо та Хатчкрофт вирішили це довести.

Вони покладалися на техніку, яку можна вважати «розширенням об’єктива». Почніть з однієї вершини. Потім зменште масштаб, щоб переглянути всі вершини, які знаходяться лише на одному ребру вихідного графа. На квадратній сітці тепер ви зможете побачити всього п’ять вершин. Знову розширте лінзу, щоб побачити всі вершини на відстані двох ребер, а потім на відстані трьох ребер, чотирьох ребер і так далі.

Easo та Hutchcroft встановлюють циферблат, який визначає, скільки посилань є поблизу місця, де вони бачили великий кластер. Потім вони розширили лінзу, спостерігаючи, як все більше і більше країв збираються у їх великому скупченні. Під час цього їм довелося збільшити ймовірність наявності зв’язків, що спрощує показ того, що граф має великий зв’язний компонент. Це тонке балансування. Їм потрібно було досить швидко розширити поле зору та додавати посилання досить повільно, щоб відкрити весь нескінченний графік без різкої зміни положення циферблата.

Вони змогли показати, що великі кластери ростуть швидше, ніж менші, тому, як сказав Easo, «ваш кластер росте все швидше і швидше, коли стає все більшим і більшим, як коли ви котите сніжний ком».

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

У 2018 році Гатчкрофт використав подібну ідею щоб довести гіпотезу локальності для швидкозростаючих графів, таких як 3-регулярне дерево. Але це не спрацювало для графіків із повільним зростанням, таких як квадратна сітка, або для графіків, які ростуть із середньою швидкістю, не відповідаючи ані математичним критеріям швидкого зростання, ані критеріям повільного зростання.

«Ось тут все стає справді розчаровуючим протягом приблизно трьох років», – сказав Гатчкрофт.

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

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

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

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

На цьому етапі дві групи математиків успішно впоралися з гіпотезою з різних напрямків: швидкого та повільного. Але це залишило значні прогалини. По-перше, існує категорія проміжного зростання, яка не була охоплена технікою Еасо та Гатчкрофта чи доказом Контрераса, Мартіно та Тасіона. Інша проблема полягала в тому, що аргументи все ще не стосувалися графіків зі змінними темпами зростання — лише тих, які залишалися швидкими чи повільними. Для застосування аргументів Контрера, Мартіно та Тасіона до довільних графіків було недостатньо того, що геометрія зрештою виглядає ручною, коли ви зменшуєте масштаб, пояснює Еасо: «Нам потрібно, щоб зараз вона виглядала ручною, близько поточного масштабу».

Середина Ніде

Транзитивні графіки проміжного зростання дуже загадкові. Математики ніколи не знайшли прикладу транзитивного графа, зростання якого потрапляє в цей діапазон. Цілком можливо, що їх навіть не існує. Але математики не довели, що їх не існує, тому будь-який повний доказ гіпотези про локальність Шрамма повинен стосуватися їх. Крім того, Easo та Hutchcroft потребували звернення до графіків, які можуть лише короткочасно мати проміжне зростання в певному масштабі довжини, навіть якщо вони ростуть швидше чи повільніше, коли ви збільшуєте чи зменшуєте масштаб.

Easo та Hutchcroft провели більшу частину минулого року, працюючи над тим, щоб поширити свої результати на графіки, які не були охоплені жодним із попередніх методів.

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

«Нам довелося кинути все, що ми знали, на проблему», — сказав Гатчкрофт.

Рішення дає математикам краще уявлення про те, що відбувається вище порогу перколяції, де ймовірність нескінченного кластера становить 100%, і нижче, де ймовірність становить 0%. Але математики все ще спантеличені тим, що відбувається саме на порозі для більшості графіків, включаючи тривимірну сітку. «Це, мабуть, найвідоміше, найосновніше відкрите питання в теорії перколяції», — сказав Рассел Лайонс Університету Індіани.

Двовимірна сітка є одним із небагатьох випадків, коли математики довели, що відбувається саме на порозі: нескінченні кластери не утворюються. І після того, як Гріммет і Марстранд довели версію гіпотези локальності для великих плит, Грімметт і його колеги показали, що якщо ви розріжете тривимірну сітку навпіл по горизонталі, створивши підлогу, і налаштуєте циферблат точно на поріг перколяції, нескінченні кластери не з’являться. Їх результат натякає на те, що повна тривимірна сітка, як і її двовимірний аналог, може не мати нескінченного кластера на порозі перколяції.

У 1996 році Бенджаміні і Шрамм здогадався що ймовірність знайти нескінченний кластер прямо на порозі дорівнює нулю для всіх транзитивних графів — так само, як і для 2D-сітки або для 3D-сітки, розрізаної навпіл. Тепер, коли припущення про локальність вирішено, розуміння того, що відбувається безпосередньо в точці переходу, може бути трохи ближчим.

виправлення: 18 Грудня, 2023
Кількість вузлів у межах n ланок початкового вузла на 3-регулярному графі зростає приблизно як 2ⁿ, а не 3ⁿ як було зазначено в цій статті. Статтю виправлено.

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