Числа Рамсея не давались математикам полвека. Решение нашлось там, где никто не искал — на поверхности сферы
Математики десятилетиями изучают вопрос, который звучит почти как задачка из детского учебника: сколько точек нужно соединить линиями, чтобы в рисунке неизбежно появился порядок? Не важно, как именно раскрашивать линии и как пытаться спрятать закономерность. Если точек станет достаточно много, внутри схемы всё равно возникнет группа, где все участники связаны между собой одинаковым способом.
Такую задачу изучает теория Рамсея. Представим несколько точек на листе бумаги. Каждая точка соединена линией с каждой другой, а каждую линию можно покрасить в красный или синий цвет. Математиков интересует момент, когда при любой раскраске обязательно появится, например, красный или синий треугольник: три точки, где все три соединяющие линии имеют один цвет.
На маленьком примере всё видно сразу. Пять точек ещё можно соединить и раскрасить так, чтобы одноцветного треугольника не было. Но стоит добавить шестую точку, и избежать красного или синего треугольника уже невозможно. Поэтому число Рамсея для трёх точек равно шести.
Можно задавать более сложные условия. Например, пытаться избежать красной группы из трёх точек и синей группы из четырёх. Восемь точек ещё допускают удачную раскраску, а девять уже заставляют получить один из запрещённых вариантов. Чем больше такие группы, тем труднее понять, где проходит граница между «ещё можно спрятать порядок» и «порядок неизбежен».
Для больших размеров точные ответы почти неизвестны. Поэтому математики доказывают оценки. Одна оценка говорит: сеть такого-то размера ещё можно раскрасить без запрещённого рисунка. Другая говорит: начиная с такого-то размера запрещённый рисунок появится обязательно. Новая работа улучшила именно первую оценку для близкого к классическому случая: исследователи доказали, что удачная раскраска может существовать для чуть более крупных сетей, чем раньше удавалось показать.
История этой задачи тесно связана с Полем Эрдёшем. В 1947 году он предложил подход, который поначалу выглядел странно. Вместо того чтобы строить нужную раскраску вручную, Эрдёш предложил выбрать цвета случайно и посчитать вероятность удачи. Если вероятность получить рисунок без запрещённой группы больше нуля, значит хотя бы один подходящий рисунок точно существует.
Так появился вероятностный метод. Сегодня его используют далеко за пределами теории графов: в дискретной математике, информатике, проверке чисел на простоту, проектировании схем и работе с данными. Метод помогает там, где нужный объект трудно показать руками, но можно доказать, что случайный выбор иногда его создаёт.
С числами Рамсея этот подход дал мощный старт, а затем почти перестал двигаться в самой трудной зоне. Особенно упорно сопротивлялись случаи, где запрещённые красные и синие группы имеют одинаковый или почти одинаковый размер. Эрдёш доказал, что для группы размера k число Рамсея больше примерно 2 в степени k/2. Для k = 1000 это даёт величину около 2^500. За десятилетия оценку удалось поднять лишь примерно до 2^501.
Новая работа изменила не саму идею случайности, а способ выбирать цвета. В классическом варианте каждая линия получает цвет независимо, как при броске монеты. Новый подход связывает цвет линии с геометрией.
Сначала точки случайно размещают на поверхности сферы в пространстве с очень большим числом измерений. Затем смотрят на расстояние между каждой парой точек. Если две точки далеко друг от друга, линию между ними красят в красный цвет. Если близко - в синий. Цвета больше не появляются отдельно друг от друга: весь рисунок зависит от расположения точек на одной общей поверхности.
Такой приём помогает бороться с большими красными группами. Чтобы получить красную группу, нужно много точек, где каждая находится далеко от всех остальных. Геометрия высокой размерности сильно ограничивает такие наборы. Но возникает риск с другой стороны: близкие точки чаще дают синие группы. Поэтому авторам нужно было доказать, что новый способ действительно помогает, а не просто переносит проблему из красного цвета в синий.
Главная часть доказательства опирается на необычное свойство пространств с большим числом измерений. Если провести линии от центра такой сферы к случайно выбранным точкам, большинство линий окажется почти под прямым углом друг к другу. Для обычной трёхмерной сферы такая картина не кажется естественной, но в высокой размерности она становится типичной. Благодаря этому расстояния между точками можно оценивать гораздо строже.
После этих оценок авторы показали: при правильных параметрах остаётся ненулевая вероятность получить раскраску без запрещённых одноцветных групп. Значит нужная раскраска существует. Доказательство заняло около года и выросло в работу примерно на 40 страниц.
Результат не решает главный диагональный случай, где красные и синие группы имеют одинаковый размер. Но он улучшает оценки для почти диагональных чисел Рамсея, например когда запрещённая красная группа примерно вдвое меньше синей. В этой зоне заметного продвижения не было около 50 лет.
Численный выигрыш очень мал. В одной формуле к прежнему основанию степени добавилась величина порядка 10^-21. И вроде как такая прибавка выглядит почти ничтожной, но в теории графов важен сам факт улучшения: старая задача снова поддалась новому приёму.
Работа уже дала продолжение. Другие математики упростили геометрическую модель и ещё немного улучшили оценки. Похожие идеи начали применять к задачам с тремя цветами, где возможных одноцветных ловушек становится больше.