Сеть может долго оставаться набором маленьких изолированных участков, а после едва заметного изменения внезапно обзавестись связями, уходящими сколь угодно далеко. Пятеро математиков доказали, что подобный резкий переход происходит для любого бесконечного транзитивного графа, то есть однородной сети, где все узлы имеют одинаковое положение с точки зрения структуры. Результат закрывает одну из главных нерешённых частей теории перколяции, над которой специалисты работали десятилетиями.
Перколяция изучает распространение по случайной сети. В простейшей модели сеть состоит из узлов и соединяющих соседние узлы рёбер. Каждое ребро независимо становится открытым с некоторой вероятностью p. При небольшом p образуются только маленькие разрозненные группы связанных узлов. После прохождения критического значения pc возникает связная структура, способная простираться на неограниченное расстояние. Подобные сети относятся к теории графов, где сложные системы представляют в виде вершин и связей между ними.
Математическая модель появилась далеко не из абстрактного интереса к сетям. В 1940-х годах Розалинд Франклин исследовала пористость угля и проникновение жидкостей и газов через микроскопические каналы. В 1957 году Саймон Бродбент и Джон Хаммерсли опубликовали математическую модель, позволявшую изучать прохождение жидкости через случайную среду. Со временем перколяцию начали применять как упрощённую модель распространения эпидемий и лесных пожаров, движения вещества через пористые материалы и некоторых фазовых переходов в физике.
Главный вопрос касался не самого существования критического порога, а скорости изменения сети возле порога. Математики ожидали резкий фазовый переход. Немного ниже pc крупные связанные области должны встречаться крайне редко, а немного выше pc большие конечные «острова», не присоединённые к бесконечной сети, тоже должны быстро исчезать. Такое свойство называют резкостью фазового перехода.
Для обычных регулярных решёток подобное поведение удалось установить несколько десятилетий назад. В 1996 году Итай Бенджамини и Одед Шрамм расширили исследование перколяции на гораздо более общий класс бесконечных транзитивных графов. Квадратная решётка относится к простейшим примерам, но в класс входят также бесконечные деревья и значительно более сложные структуры, которые трудно представить геометрически.
Нижнюю половину задачи удалось закрыть раньше. Для вероятностей меньше pc математики доказали, что шанс встретить очень большой связный кластер уменьшается экспоненциально. В 2007 году результат распространили на квазитранзитивные графы. Сверхкритическая область оставалась значительно сложнее: требовалось показать, что при любом p выше критического значения большие конечные кластеры тоже становятся чрезвычайно редкими.
Сахар Дискин, Филип Исо, Ритвик Раманан Радхакришнан, Бенни Судаков и Венсан Тассьон доказали именно недостающую часть. Для любого p выше pc вероятность того, что выбранный узел окажется внутри большого, но конечного кластера, падает экспоненциально с ростом минимальной границы, необходимой для отделения подобного кластера от остальной сети. Проще говоря, крупному «острову» всё труднее оставаться изолированным: увеличение размера создаёт всё больше возможностей случайно соединиться с бесконечной структурой.
Доказательство также показывает, что длинные конечные пути, уходящие далеко от исходной точки, но так и не присоединяющиеся к бесконечной компоненте, становятся экспоненциально менее вероятными с увеличением расстояния. Поэтому переход выше критического порога действительно оказывается резким, причём вывод не зависит от конкретной геометрии транзитивного графа.
Ключевую роль сыграла техника, известная как sprinkling, или «посыпание». При таком подходе небольшую часть случайных открытий рёбер отделяют от основной конфигурации и используют позже для создания дополнительных связей. Команда обнаружила, что анализ небольшой добавочной части в обратном порядке радикально упрощает доказательство. Перестановка шагов позволила отказаться от специальных геометрических свойств решёток и получить результат сразу для всех бесконечных транзитивных графов.
Новая теорема не вычисляет универсальное значение pc и не означает, что реальная компьютерная сеть внезапно «затопится» после достижения конкретного числа соединений. Критическая вероятность зависит от структуры графа. Значение работы заключается в гораздо более общем выводе: после прохождения собственного критического порога широкий класс случайных сетей неизбежно переходит в сверхкритический режим резко, а крупные изолированные области быстро становятся маловероятными.
У теории перколяции при этом остаётся одна из знаменитых нерешённых задач. Для трёхмерной решётки математики до сих пор не знают, существует ли бесконечный кластер ровно в критической точке p = pc. Новое доказательство описывает поведение по обе стороны порога, но граница между двумя режимами продолжает скрывать отдельную загадку.
