Почему одной карты мало для всех лабиринтов ✛ ✎

Оригинал: "Obstructions to coarse universality for finitely generated groups"
· Robin Tucker-Drob
arXiv:2607.00963 · 2026-07-01 · arXiv non-exclusive · собственный разбор · 2 мин
Какую карту ни возьми, всегда найдётся сеть дорог, которая на неё не поместится.

Картограф кладёт на стол большой лист бумаги. Его задача — уместить на нём все возможные дорожные сети: прямые магистрали, запутанные лабиринты, паутины просёлочных дорог. Разрешается немного растягивать или сжимать расстояния — как если глядеть через мутное стекло. Но главное, чтобы каждая сеть узнавалась. Робин Такер-Дроб доказал: такой универсальной карты не существует.

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

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

Но математики создали одну хитрую сеть-монстр, которая вбирает в себя все сложные сети-препятствия, как матрёшка. При её строительстве они применили малое сокращение — метод склейки гигантского пазла, где каждый кусочек повторяется очень редко. Дополнительно шла пометка дорог — особые знаки, чтобы длинные пути не повторялись. Эта монстр-сеть уже не вписывается ни в какую карту с ограниченной точностью. Мечта о единой картинке разбивается.

Вывод прост: не ищи единственный шаблон. Каждый ландшафт уникален. Учёные ищут способы ослабить ограничения — вдруг всё-таки удастся создать почти универсальную карту? А метод сборки монстра пригодится и для динамических систем — например, чтобы понять, как со временем меняется паутина связей в экосистеме. И всё же лист на столе картографа навсегда останется неполным.

Число различных дорожных сетей из 100 точек без коротких петель превышает количество атомов в наблюдаемой Вселенной. Чтобы просто перечислить их все, не хватит памяти всех компьютеров мира.

N(s) \le A^s
число классов растёт не быстрее экспоненты с основанием A, зависящим от L, M и целевого графа
M(s) \ge (a s)^{3s/2}
число таких графов растёт быстрее экспоненты от s log s, за счёт показателя 3s/2 в показателе
Учёные
George Gabriel StokesPythagorasLeonhard Euler
Понятия
группа гомотопия центральная предельная теорема