ИИ Google улучшил 5 границ в теории Рамсея — некоторые держались с 2006 года
habr.comИсследователи из 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.
