СЛУЧАЙНЫЕ СЕТИ ПЕРЕСТАЮТ БЫТЬ РАСКРАШИВАЕМЫМИ ПРИ ФИКСИРОВАННОЙ ПЛОТНОСТИ
Возьмите граф — точки, соединённые связями, — и коробку цветов. Правильная раскраска в q цветов присваивает каждой точке один из q цветов так, чтобы две связанные точки никогда не получали одинаковый цвет. При небольшом числе связей это легко. При большом — становится невозможно.
Теперь построим граф случайно: n точек, каждая пара соединяется независимо с малой вероятностью, так что у точки в среднем d соседей. С ростом d случайный граф переходит от состояния «почти наверное раскрашиваем в q цветов» к состоянию «почти наверное нет». Где именно происходит переключение? Этому вопросу — для любого фиксированного числа цветов q начиная с трёх — посвящена новая статья Gaia Carenini из Кембриджского университета.
Переключение, которое может колебаться
В статье 1999 года, указанной в списке литературы, Achlioptas и Friedgut доказали, что переход резкий: для каждого размера n существует критическая средняя степень d_q(n), такая что чуть ниже неё граф почти наверное раскрашиваем, а чуть выше — почти наверное нет. Окно, в котором происходит переключение, сжимается до нуля.
Но это оставляло лазейку. Ничто не мешало самому критическому значению колебаться по мере роста графов — находиться в одном месте для графов одного размера, чуть в другом для более крупных и так и не устанавливаться. Гипотеза сходимости Achlioptas–Friedgut утверждает, что этого не происходит: для каждого q существует единственная константа d_q, ниже которой случайные графы раскрашиваемы, а выше — нет.
Что предсказывали физики
У статистической физики была своя картина происходящего. По мере добавления связей допустимые раскраски группируются в кластеры: раскраски внутри одного кластера похожи друг на друга, а два кластера различаются на многих точках. Затем, на стадии, называемой конденсацией, горстка крупных кластеров вмещает существенную долю всех раскрасок — и лишь позже множество раскрасок становится пустым. Такая организация объясняет, почему рассуждения, основанные на подсчёте, буксуют вблизи порога.
Для большого числа цветов предыдущие работы уже зажали порог в узкий диапазон: он лежит примерно между 2q log q − log q − 2 log 2 и 2q log q − log q − 1, то есть в зазоре шириной 2 log 2 − 1 при растущем q. Но «узкий» ещё не значит «фиксированный», а для малого числа цветов, например трёх, вопрос оставался открытым.
Сначала — задача-близнец
У раскраски есть близнец: выполнимость (satisfiability) — задача выбора значений «истина» или «ложь» для переменных так, чтобы выполнялся весь список случайных логических ограничений. Там тоже было известно, что резкий порог существует, но не было доказательства того, что он устанавливается. В отчёте Carenini 2026 года, на который ссылается статья, объявлено доказательство того, что он устанавливается, — для любой длины ограничений начиная с трёх: показано, что окно перехода очень узкое. Новая статья переносит это рассуждение на раскраску.
Пары, замороженные вместе
Доказательство продвигается через цепочку сведений. Будем добавлять случайные связи по одной, и пусть H — момент, когда граф перестаёт быть раскрашиваемым. Если H мало меняется от одного случайного графа к другому — в пределах окна примерно n/(log n)² связей, — то порог обязан установиться. Классическое неравенство превращает это в вопрос о последнем раскрашиваемом графе: сколько новых случайных связей он в среднем выдерживает?
Здесь появляется ключевое понятие: замороженные пары. Две точки образуют замороженную пару, когда любая допустимая раскраска даёт им один и тот же цвет. Новая связь фатальна ровно тогда, когда соединяет такую пару. Отдельные точки не могут быть заморожены в каком-то определённом цвете, поскольку перестановка цветов всегда даёт другую допустимую раскраску; вынужденным оказывается отношение между двумя точками. Carenini отслеживает, как растут эти замороженные классы при добавлении связей, удаляя связь или целую точку и наблюдая за вновь появляющимися вариантами. Оценки показывают, что последний раскрашиваемый граф не может продержаться долго, и это сужает окно достаточно, чтобы доказать гипотезу.
Что остаётся неизвестным
Теорема утверждает, что порог d_q существует для любого q ≥ 3. Она не говорит, где он находится: в статье не приводится его значение даже для трёх цветов. Статья — препринт, написанный без соавторов, и она не прошла рецензирование. В конце стоит короткое заявление о том, что ни одно из её математических рассуждений не было сгенерировано большой языковой моделью.
