Порядок ховається усередині хаосу. Саме це є головне завдання теорії Рамсея.
Десять років математики намагалися знайти цей порядок. Прогрес був “леденячим”.
Вони хотіли зрозуміти, коли перестає працювати випадковість. Коли структура стає обов’язковою.
Про що йдеться? Про графи.
Не про діаграми з гістограмами. Про мережі. Крапки, з’єднані лініями.
Уявіть собі авіамаршрути. Або дружні зв’язки. Або молекули.
Будь-який досить великий граф містить дві речі.
Кліку. Групу, де всі знають усіх.
Або “незалежна безліч”. Зграю людей, які знають нікого.
R(3,10). Ось питання. Наскільки великим має бути соціальний граф, щоб гарантувати наявність трьох спільних друзів чи десяти незнайомців?
Ми не знаємо відповіді.
Точні значення відомі менш як для тридцяти чисел Рамсея. Інші залишаються загадкою.
Тому математики використовують межі. Це пастка.
Уявіть собі сміттєпрес з «Зоряних війн». 🤖
Нижня межа – це одна стіна. Верхня межа – інша.
Десятиліттями розрив між ними був величезним.
Тут з’явився Домагож Брадач.
Він працює у Швейцарській вищій технічній школі Цюріха (ETH Zurich). Минулого місяця він опублікував доказ, який зруйнував бар’єр.
Стіни зімкнулися. Близько. Чудово близько.
Ось як це йому вдалося.
“Геометрію ми розуміємо набагато краще, ніж теорію графів”, – Марсело Кампос.
Брадач не починав із хаосу. Він почав із геометрії.
Спочатку він збудував гігантський граф. Жорсткий. Алгебраїчний. Структурований.
Навіщо?
Тому що геометрія надає вам властивості безкоштовно.
Потім додав хаос.
Він довільно розрізав свій великий геометричний граф. Взяв шматок. Вилучив кілька поганих вузлів.
Результат?
Графи, що розрослися до величезних розмірів. Але уникли патернів.
Ні клік. Ні великих незалежних множин.
Лише балансуючи на межі.
Найкраща верхня межа? Застигла з 1930-х років. Брадач майже торкнувся її.
«В ідеальному світі я просто сказав би: ось граф. І було б справу зроблено», — Домагож Брадач.
На жаль, світ не є ідеальним.
Він довів, що такі графи можуть існувати. Але не надав їх у явному вигляді. Це “імовірнісний метод”. Винайдений Паулем Ердешем. Доказ існування через випадковість.
Доказ Брадача був добрим. Але то був не кінець історії.
На сцену виходить ІІ.
OpenAI побачили статтю. Сгодуй її своєї моделі для міркувань.
ІІ знайшов нюанс.
Чи не заміну. А шліфування.
Він усунув крихітну частку невизначеності, що залишилася в межах Брадача.
Тепер нижня та верхня межі збігаються з точністю до полілогарифмічних розривів.
Майже ніщо.
Гра закінчена?
Ще ні.
«Ми систематично не намагаємося виправляти статті з arXiv. Нам просто пощастило», – Мехтааб Сахней (OpenAI).
ІІ не вирішив все. Він лише підкрутив гайки у роботі Брадача.
Марсело Кампос любить нагадувати нам, хто виконав основну роботу. Ідея належить людині. ІІ просто підчистив краї.
Проте.
ІІ покращив вирішення математичної проблеми, якій майже сто років. Протягом кількох тижнів.
Хто б міг подумати?
Ми стоїмо впритул до істини чисел Рамсея.
Розрив тонкий. Як лід у квітні.
Настаньте на нього і подивіться, що зламається.
