Новые границы чисел Рэмси: прорыв 2023 года
В марте 2023 года математики из Оксфорда и Сан-Паулу улучшили верхнюю границу симметричных чисел Рэмси R(5,5) с 43 до 39, а также добились прогресса для асимметричных случаев впервые с 1935 года. Числа Рэмси определяют размер графа, гарантирующий наличие монохроматических клик.
Новое доказательство использует вероятностные методы, локальную лемму и SAT-solvers. Результат сократил разрыв между верхней и нижней границами на порядки. Это имеет критические приложения в комбинаторике, информатике и криптографии. Работа опубликована в Annals of Mathematics.