Дуже великий маленький стрибок у теорії графів

15 березня інтригуючі оголошення про семінар викликали гуркіт у галузі комбінаторики, математичного вивчення рахунку. Наступного дня троє співробітників планували провести скоординовані переговори. Джуліан Сахасрабудхе звернувся б до математиків у Кембриджі, Англія Саймон Гріффітс поділився б новинами в Ріо-де-Жанейро та Марсело Кампос в Сан-Паулу. Усі три доповіді носили ідентичні назви та загадкові анотації з двох речень, які посилалися на «останній прогрес у старій проблемі Ердеша». Поки Пауль Ердеш, угорський математик, який помер у 1996 році, позував сотні проблем протягом його кар'єри комбінатори швидко вгадали конкретну тему, про яку тріо планувало говорити. Ходили чутки про так зване число Рамсея, одне з найважчих для обчислення величин у всій математиці.

Числа Рамсі породили цілу дисципліну під назвою теорія Рамсі, яка шукає неминучі закономірності у величезному діапазоні систем.

Наприклад, скажімо, ви намагаєтеся розподілити всі цілі числа між кількома відрами, і ви хочете уникнути розміщення послідовностей рівномірних чисел у будь-якому з відер. Теорія Рамсі показує, що ви зазнаєте невдачі (якщо у вас немає нескінченно багато відер). Теорію можна застосувати майже до всього, що ви можете порахувати. Його головний урок полягає в тому, що «ви не можете створити повністю хаотичну систему», — сказав Бенні Судаков, математик зі Швейцарського федерального технологічного інституту Цюріха.

Число Рамсі кількісно визначає, наскільки великим має бути парадигматичний приклад, перш ніж неминуче виникнуть певні шаблони. Але, незважаючи на його центральність, ніхто не зміг обчислити число Рамсі для всіх, крім найпростіші екземпляри. Найкраще, що вони змогли зробити, це знайти обмеження (або рамки) того, що це може бути. Навіть тоді верхня межа, вперше встановлена ​​Ердешем і його колегою майже століття тому, ледь змінилася.

Потім на семінарах 15 березня та в статті, опублікованій пізніше того вечора, дослідники оголосили, що вони покращили верхню межу числа Рамсі на експоненціальну величину.

«Я був розбитий», сказав Юваль Вігдерсон, математик з Тель-Авівського університету, почувши про новий результат. «Півгодини-годину я буквально тремтів».

Лінія партії

Теорія Рамсі найчастіше ставить запитання про цілі числа або про графіки. У цьому контексті графік означає сукупність точок, званих вузлами, з’єднаних лініями, званими ребрами, які можуть мати такі властивості, як довжина або, як у випадку з числами Рамсі, колір.

Повний граф і складний, і простий — кожен вузол пов’язаний з кожним іншим вузлом. Число Рамсі описує, скільки вузлів повинен містити повний граф, щоб він мав певну структуру. Скажімо, ребра повного графа мають один із двох кольорів: червоний або синій. Скажімо, ви намагаєтеся розфарбувати ребра таким чином, щоб уникнути з’єднання групи вузлів із ребрами одного кольору. У 1930 році Френк Ремсі довів, що якщо граф достатньо великий, стає неможливо уникнути створення того, що математики називають монохроматичною клікою — групи вузлів, спільні краї яких або всі червоні, або всі сині.

Наскільки великим має бути графік, перш ніж виникне монохроматична кліка? Відповідь залежить від розміру кліки. Рамсі показав, що існує число, яке тепер називається числом Рамсі, яке представляє мінімальну кількість вузлів, для яких повинна існувати монохроматична кліка заданого розміру, незалежно від того, як пофарбовані ребра.

Але розмір числа Рамсі визначити важко. У 1935 році, через п’ять років після того, як Рамсі показав, що воно існує, Ердеш і Джордж Секереш запропонували нову, точнішу верхню межу того, наскільки великим є число Рамсі для кліки певного розміру. Але відтоді математики майже не змогли покращити розрахунки Ердеша та Секереша.

Щоб краще зрозуміти, що це означає, розглянемо класичний приклад, у якому вузли представляють гостей на вечірці. Пофарбуйте межу між будь-якими двома гостями в червоний колір, якщо вони зустрічалися раніше, і в синій, якщо ні. Ви можете вибрати будь-який розмір кліки — запросіть на вечірку достатньо людей, і ви не зможете уникнути запрошення групи людей, які всі знають один одного (клік у багатьох значеннях цього слова), або групи людей, які ніколи раніше не зустрічалися.

«Найпростіша річ, яку можна мати на графіку, — монохроматична кліка», — сказав Марія Чудновська, математик Прінстонського університету. «Дивно, що в кожному величезному графіку можна знайти такий великий. Це абсолютно незрозуміло».

Перші кілька чисел Рамсі відносно легко обчислити. Припустімо, ви хочете знати розмір найменшого графа, який неминуче повинен містити кліку розміру два, або R(2) для математиків. Оскільки повний граф із двома вузлами — це лише два вузли, з’єднані ребром, і це ребро має бути або червоним, або синім, R(2) дорівнює 2. Більш загально, R(k), або число Рамсі k, — це мінімальна кількість вузлів, за межами якої граф не може уникнути кліки розміру k.

Не так вже й важко показати, що число Рамсі для кліки розміром 3 або R(3) дорівнює 6 (див. графік). Але лише в 1955 році R(4) було встановлено на рівні 18. R(5) залишається невідомим — це щонайменше 43 і не більше 48. Хоча ці цифри невеликі, просіяти всі можливі кольори неможливо. питання, сказав Девід Конлон з Каліфорнійського технологічного інституту. Розглянемо кількість розмальовок на повному графі з 43 вузлами. «У вас 903 ребра; кожен із них можна розфарбувати двома способами», – пояснив він. «Тож ви отримуєте 2⁹⁰³, що просто астрономічно велике».

Зі збільшенням розміру кліки завдання визначення числа Рамсі стає лише складнішим. Ердеш пожартував, що тотальна війна з інопланетянами, які потребують математики, буде легшою, ніж спроба розрахувати R(6), що знаходиться десь між 102 і 165. Діапазон невизначеності швидко зростає: оцінки склав Станіслав Радзішовський, R(10) може бути від 798 до 23,556 10. Але цілі математиків сягають далеко за межі числа Рамсея XNUMX. Вони хочуть формулу, яка дасть хорошу оцінку R(k), навіть — або особливо — коли k є надзвичайно великим.

«Я не знаю жодної людини в комбінаториці, яка хоча б трохи не замислювалася над цією проблемою», — сказав Вігдерсон. «Ця проблема, я вважаю, справді особлива».

Порядок в суді

Френк Ремсі був еклектичною, блискучою фігурою, яка померла, коли йому було 26 років. За кілька тижнів до смерті, Праці Лондонського математичного товариства опублікований папір в якому він ввів числа Рамсі. Ця робота була навіть не про графіки, а про проблему математичної логіки. Ремсі довів, що твердження, яке задовольняє певні умови, повинно бути істинним принаймні деякий час. Одна з цих умов полягала в наявності великого «всесвіту» сценаріїв для перевірки твердження. Як сходинку до цього результату Рамсі показав, що число Рамсі є кінцевим.

Через п'ять років Ердеш і Секереш показали, що число Рамсі k менше 4^k. І через 12 років, Ердеш показав що він більший, ніж приблизно $latex sqrt{2}^k$. Для цього він підрахував шанси того, що граф із випадково пофарбованими ребрами містить монохроматичну кліку. Ця «імовірнісна» техніка мала величезний вплив на теорію графів. Він також захопив R(k) між двома стійками воріт, що експоненціально зростають: $latex sqrt{2}^k$ і $latex 4^k$.

З плином десятиліть численні математики намагалися скоротити розрив між можливими значеннями числа Рамсі. Деяким це вдалося: у 1975 році Джоел Спенсер подвоїв нижню межу. І серія робіт о Конлон, Ендрю Томасон та Ашвін Сах зсунув верхню межу приблизно на $latex 4^{log(k)^2}$ до 2020 року. Але порівняно з розмірами меж числа Рамсі ці коригування були невеликими. Навпаки, будь-яке скорочення до 4 у формулі Ердеша та Секереша R(k) < 4^k буде експоненціальним покращенням, яке швидко зростатиме k стає більшим.

«Здається, це просто миле запитання», — сказав Роб Морріс, математик із IMPA, Бразильського інституту чистої та прикладної математики в Ріо-де-Жанейро, який є співавтором нового результату разом з Кампосом, Гріффітсом і Сахасрабудхе. «Це трохи тонко оцінити. Але люди справді дбають про це». Можливо, це заниження. «Якби вони довели це в 1936 році, люди б сказали: гаразд, так у чому ж справа?» сказав Бела Боллобас, який був докторським радником Морріса та Сахасрабудхе в Університеті Мемфіса. «З тих пір було доведено, що це дуже велика проблема, тому що протягом багатьох років було написано кілька тисяч робіт про різні варіанти проблеми Рамсі». як Ліана Єпремян, математик з Університету Еморі, сказав: «Числа Рамсі створюють міст між комбінаторикою, ймовірністю та геометрією».

Теорія гри

 У серпні 2018 року Сахасрабудхе був докторантом під керівництвом Морріса в IMPA. Вони сподівалися розпочати новий проект із Гріффітсом, який викладає в сусідньому Папському католицькому університеті, коли стаття Конлона привернув їхню увагу. У документі викладено можливу стратегію отримання експоненційного покращення числа Рамсі. Гріффітс, Морріс і Сахасрабуде почали грати з цією ідеєю.

«Спочатку це було дуже захоплююче, — згадував Сахасрабудхе. За його словами, їм знадобився лише місяць, щоб скласти ескіз своєї аргументації.

Їх план полягав у тому, щоб спиратися на ідеї, використані в оригінальному доказі Ердеша та Секереша, що $latex R(k) < 4^k$. Щоб довести, що число Рамсі не перевищує  $latex 4^k$, уявіть собі гру на повному графі з $latex 4^k$ вузлами. У грі є два гравці. По-перше, ваш опонент забарвлює кожен край у червоний або синій колір, сподіваючись забарвити краї таким чином, щоб уникнути створення монохроматичної кліки k вузли.

Коли опонент закінчить розфарбовувати, ваше завдання — шукати монохроматичну кліку. Якщо ви знайдете один, ви виграєте.

Щоб виграти цю гру, ви можете слідувати простій стратегії. Це допомагає подумати (метафорично) про сортування ваших вузлів у два відра. Вузли в одному відрі утворять синю кліку, а вузли в іншій утворять червону кліку. Деякі вузли буде видалено, і про них більше ніколи не буде чути. На початку обидва відра порожні, і кожен вузол є кандидатом на входження в будь-який з них.

Почніть з будь-якого вузла, який вам сподобається. Потім подивіться на з’єднувальні краї. Якщо половина або більше ребер червоні, тоді видаліть усі сині ребра та вузли, до яких вони підключені. Потім помістіть свій початковий вибір у «червоне» відро. Усі червоні грані цього вузла все ще живі та здорові, чіпляючись за решту графіка зсередини відра. Якщо більше половини країв сині, аналогічно видаліть червоні краї та вузли та помістіть його в синє відро.

Повторюйте, поки у вас не залишиться вузлів. (Оскільки граф завершено, кожен залишився вузол у будь-якій точці підключається до обох сегментів, поки не буде розміщено в одному з них.)

Коли закінчите, загляньте всередину відер. Оскільки вузол потрапив у червоне відро лише після того, як його сині сусіди були усунені, усі вузли в червоному відрі з’єднані червоними краями — вони утворюють червону кліку. Так само синє відро утворює синю кліку. Якщо ваш вихідний граф має принаймні $latex 4^k$ вузлів, можна довести, що одне з цих відер повинно містити принаймні k вузлів, що гарантує монохроматичну кліку у вихідному графі.

Цей аргумент розумний і елегантний, але він змушує вас створити дві кліки — одну синю й одну червону — навіть якщо насправді вам потрібна лише одна. Конлон пояснив, що було б ефективніше завжди йти на червоний колір. За цією стратегією ви вибираєте вузол на кожному кроці, стираєте його сині краї та кидаєте його в червоне відро. Тоді червоне відро швидко заповниться, і ви накопичите червону кліку k вузлів вдвічі швидше.

Але ваша стратегія має працювати для будь-якого червоно-синього забарвлення, і важко знати, чи завжди можна знайти вузол із великою кількістю червоних країв. Таким чином, дотримуючись пропозиції Конлона, ви ризикуєте натрапити на вузол, до якого майже немає червоних країв. Це змусило б вас видалити величезну частину графіка одночасно, залишаючи вас намагатися створити свою кліку, перш ніж у вас закінчаться вузли. Щоб реалізувати пропозицію Конлона, Гріффітсу, Моррісу та Сахасрабуде потрібно було довести, що цього ризику можна уникнути.

Іспит з відкритої книги

Оновлюючи свій ігровий процес, Ґріффітс, Морріс і Сахасрабудхе пішли трохи окружнішим шляхом. Замість того, щоб будувати монохроматичну кліку безпосередньо, кидаючи вузли в їхні червоні та сині відра, вони спочатку зосередилися на створенні структури під назвою червона книга.

У теорії графів книга складається з двох частин: монохроматична кліка, яка називається «хребтом», і другий, окремий кластер вузлів, який називається «сторінками». У червоній книзі всі краї, що з’єднують вузли корінця, червоні, як і краї, що з’єднують корінець зі сторінками. Однак краї, що з’єднують вузли на сторінках, можуть мати будь-яку комбінацію кольорів. Конлон зазначив у своїй статті 2018 року, що якщо ви можете знайти червону кнопку всередині сторінок книги, ви можете поєднати її з корінцем, щоб отримати більшу червону кнопку. Це дає змогу розділити пошук великої червоної кліки на два простіші пошуки. Спочатку шукайте червону книгу. Потім шукайте клік на сторінках книги.

Гріффітс, Морріс і Сахасрабудхе хотіли налаштувати алгоритм, який виграв гру, щоб він створив червону книгу замість червоної кліки. Незважаючи на те, що вони зупинилися на цьому плані лише через кілька тижнів після початку проекту, знадобилися роки, щоб змусити його запрацювати. Їм ще потрібно було відвернути загрозу втрати всіх своїх червоних країв.

«Ми застрягли дуже довго», — сказав Кампос, який приєднався до проекту у 2021 році.

Цього січня четверо математиків домовилися перейти до іншої версії задачі. Ця версія звучить складніше, але вона виявилася простішою.

Увесь час команда була зосереджена на числі Рамсі R(k), також відоме як «діагональне» число Рамсі. Графік розміру R(k) має містити k вузли, усі з’єднані ребрами одного кольору, але не має значення, червоний чи синій цей колір. З іншого боку, “недіагональне” число Рамсі R(k, l) вимірює, наскільки великим має бути графік, перш ніж він міститиме червону кнопку з k вузлів, або синій клік з l вузлів. Замість того, щоб продовжувати зламувати діагональну проблему, група вирішила спробувати недіагональну версію. Це виявилося показовим.

«Довгий час здавалося, що всі двері, до яких ти штовхаєш, були або зачинені на засув, або, принаймні, досить важко пройти», — сказав Гріффітс. «І після цієї зміни ви просто відчули, що всі двері були відкриті. Якимось чином все просто спрацювало». У недіагональній версії вони знайшли спосіб видалити купу синіх країв одночасно, дотримуючись певного протоколу, що збільшило щільність червоних країв і призвело до покращеного обмеження недіагонального числа Рамсі. Цей метод, який називається аргументом «приросту щільності», раніше використовувався для вирішення інші важливі проблеми комбінаторики, але він не використовувався для проблеми числа Рамсі.

Тоді четверо математиків використали нову межу недіагонального числа Рамсі, щоб розчистити шлях для діагонального результату. На початку лютого вони нарешті знизили межу числа Рамсея на експоненціальний коефіцієнт — досягнення, якого математики прагнули майже століття. І вони зробили це шляхом модернізації тієї самої аргументації, яку Ердеш і Секереш висунули в 1935 році.

Епсилон, Епсилон

Після переговорів 16 березня учасники почали підтверджувати чутки. Фотографії з виступу Сахасрабудхе поширювалися через телефонні дзвінки та приватні повідомлення — навіть у нечіткий, але навідний пост у блозі математика Гіла Калая. Кампос, Гріффітс, Сахасрабудхе та Морріс стверджували, що показали, що $latex R(k) < 3.993^k$. Тієї ночі чотири автори опублікували свою статтю в Інтернеті, дозволяючи математикам побачити новий доказ на власні очі.

«Я думаю, що багато хто з нас не очікували такого покращення протягом свого життя, по суті», — сказав Матія Буціч, математик Прінстонського університету та Інституту перспективних досліджень. «Я вважаю, що це абсолютно приголомшливий результат».

Багато експертів сподіваються, що з падінням експоненціального бар’єру швидко почнеться більший прогрес. Автори нової статті навмисне не розширювали свій метод до меж, щоб не затьмарювати свою аргументацію непотрібними деталями. «Мене дуже цікавить, наскільки далеко може зайти цей метод, тому що я поняття не маю», — сказав Кампос.

«Це надзвичайно геніальний, абсолютно чудовий доказ і справжній прорив. Тож тепер я очікую, що шлюзи будуть відкриті», – сказав Боллобас. «Я переконаний, що через три роки дискусія буде йти про можливі покращення. Чи можемо ми покращити 3.993 до 3.9? Може до 3.4? А як щодо 3?»

Новий доказ складається з 56 сторінок, і знадобляться тижні, щоб кожна деталь була повністю перевірена спільнотою комбінаторики. Але колеги налаштовані оптимістично. «Ця група авторів, вони дуже серйозні люди. І це люди, які дійсно, дуже добре розбираються в дуже технічних речах», – сказав Вігдерсон.

Коли мова йде про його співробітників, Гріффітс погоджується. «Це привілей працювати з геніальними людьми, чи не так? І я думаю, що це те, за що я відчуваю велику вдячність", - сказав він. «Якби вони залишили це мені, мені знадобилося б ще п’ять років, щоб правильно розібратися».