ИИ Google улучшил 5 границ в теории Рамсея — некоторые держались с 2006 года

Исследователи из Google и Google DeepMind опубликовали работу, в которой с помощью AlphaEvolve улучшили нижние границы для пяти классических чисел Рамсея — R(3,13), R(3,18), R(4,13), R(4,14) и R(4,15). Каждая из границ выросла на единицу, но в теории Рамсея, где прогресс измеряется десятилетиями, это заметный результат: предыдущий рекорд для R(3,18) был установлен в 2006 году, для R(3,13), R(4,13) и R(4,14) — в 2015-м, для R(4,15) — в 2020-м.

Числа Рамсея — классическая задача комбинаторики: R(r,s) показывает, сколько вершин нужно графу, чтобы в нем гарантированно нашлась клика размера r или независимое множество размера s. Точные значения известны лишь для совсем маленьких параметров, а для остальных математики десятилетиями двигают нижние и верхние границы. Поль Эрдёш когда-то заметил: если инопланетяне потребуют вычислить R(5,5), человечеству стоит бросить на это все ресурсы, а вот для R(6,6) — лучше сразу атаковать инопланетян. Впрочем, сказано это было в 1990 году — и, как мы видим, возможности человечества выросли.

До сих пор каждый сдвиг нижней границы требовал узкоспециализированного алгоритма, заточенного под конкретную пару (r,s). Авторы пошли другим путем: AlphaEvolve использовался как единый метаалгоритм, который сам порождал поисковые процедуры для каждого случая. Система стартовала с пустого графа и эволюционно наращивала программы поиска, а не конструкции фиксированного размера. Обнаруженные алгоритмы разделились на четыре семейства — от случайной инициализации и алгебраических затравок (графы Пэли, кубические вычеты) до циклических конструкций и гибридных спектрально-фрактальных подходов.

Впрочем, сами по себе сдвиги на единицу — не главный результат работы. Числа Рамсея здесь скорее полигон: задача с четким