Очень большой маленький скачок вперед в теории графов

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 году Джоэл Спенсер удвоил нижний предел. И серия статей Conlon, Эндрю Томасон и Эшвин Сах опустил верхний предел примерно в $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 марта присутствующие стали подтверждать слухи. Фотографии выступления Сахасрабудхе разошлись по телефону и в личных сообщениях — даже в невнятный, но наводящий на размышления пост в блоге математика Гила Калаи. Кампос, Гриффитс, Сахасрабухе и Моррис утверждали, что показали, что $латекс R(k) < 3.993^k$. В ту ночь четыре автора разместили свою работу в Интернете, позволяя математикам увидеть новое доказательство своими глазами.

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

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

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

Новое доказательство занимает 56 страниц, и потребуется несколько недель, чтобы каждая деталь была полностью проверена сообществом комбинаторики. Но коллеги настроены оптимистично. «Эта группа авторов, они очень серьезные люди. И это люди, которые очень хорошо разбираются в очень технических вещах», — сказал Вигдерсон.

Что касается его сотрудников, Гриффитс соглашается. «Это привилегия работать с блестящими людьми, не так ли? И я думаю, что именно за это я очень благодарен», — сказал он. «Если бы они предоставили это мне, мне, возможно, потребовалось бы еще пять лет, чтобы уточнить детали».