Несколько десятилетий назад Пол Эрдёш использовал принцип случайности, чтобы сделать обширный и странный мир сетей чуть более понятным. Теперь математики делают его метод ещё более эффективным.
В 1947 году Пол Эрдёш, венгерский математик-передвижник, представил то, что впоследствии стало одним из самых мощных инструментов математики. Он хотел доказать существование определённого вида объектов — в данном случае сети, состоящей из взаимосвязанных узлов. Но, как ни странно, в его доказательстве не указывалось, как именно её построить. Вместо этого он показал, что если рассмотреть все возможные сети и выбрать одну из них наугад, вероятность того, что вы найдёте сеть с нужным свойством, больше нуля. Это означает, что искомая сеть где-то существует, даже если вы почти ничего о ней не знаете.
Подход Эрдёша, известный как вероятностный метод, был простым, но революционным. До его появления «если бы я заявил, что определённые объекты должны существовать, вы бы ответили: „Покажите мне такой объект“, — сказал Бенни Судаков, математик из Швейцарской федеральной политехнической школы в Цюрихе. — Но некоторые объекты настолько необычны, что нам трудно даже представить, что они вообще существуют».
Метод Эрдёша преодолел эту трудность, продемонстрировав, что случайность можно использовать способами, о которых математики и не подозревали. «Тогда было просто поразительно, что случайность можно использовать таким образом, — сказал Джоэл Спенсер из Нью-Йоркского университета. — Теперь это стало базовым подходом».
Сегодня вероятностный метод применяется во всех областях математики и информатики — для определения простоты чисел, проектирования более эффективных схем или очистки данных без введения систематических ошибок.
Исследователи усовершенствовали этот метод различными способами. Однако в отношении первоначальной задачи вероятностного метода — вопроса о сетях, на который стремился ответить Эрдёш, — прогресс был весьма незначительным. На протяжении восьми десятилетий математики не смогли существенно улучшить решение, предложенное Эрдёшем.
Теперь ситуация, наконец, начинает меняться.
Глас вопиющего в пустыне
Представьте себе сеть узлов — граф — в которой каждая пара узлов соединена ребром.
Теперь раскрасьте рёбра, выбирая либо красный, либо синий цвет, но с одним ограничением: не создавайте больших скоплений узлов, в которых все узлы соединены рёбрами одного цвета. Эти запрещённые структуры называются монохроматическими кликами. Вот монохроматическая клика, состоящая из трёх узлов, которую математики называют кликой размера 3:
Если в вашем графе достаточно узлов, избежать образования монохроматической клики будет невозможно, как бы вы ни раскрасили рёбра. Например, если вы хотите избежать клики размера 3, ваш граф может иметь не более пяти вершин. Граф с шестью вершинами всегда будет содержать такую клику:
Поэтому математики говорят, что «число Рамсея» для клики размера 3, обозначаемое R(3), равно 6. Числа Рамсея показывают, насколько большими могут быть графы, прежде чем неизбежно возникнет запрещённая структура.
Числа Рамсея для красных и синих клик могут быть разными. Например, можно раскрасить граф с восемью вершинами так, чтобы в нём не было ни одной красной клики размера 3 или синей клики размера 4. Но если добавить в граф ещё одну вершину, то придётся создать как минимум одну красную или синюю клику. Следовательно, число Рамсея R(3, 4) равно 9.
По мере того как клики, которых вы хотите избежать, становятся больше, задача становится всё сложнее и сложнее. Математикам удалось вычислить лишь несколько самых маленьких чисел Рамсея. «Очень трудно создавать что-то, не имеющее структуры, — сказал Пол Хорн из Университета Денвера. — Возможно, потому, что мы люди и мы подвержены собственным предубеждениям».
Итак, математики десятилетиями пытались найти всё более точные приближения к числам Рамсея. Именно этим занимался Эрдёш, когда в 1947 году предложил свой вероятностный метод. Вместо того чтобы непосредственно строить графы, свободные от клик, он рассмотрел все возможные способы раскраски графа, а затем показал, что по крайней мере некоторая ненулевая часть этих раскрасок обязательно должна быть свободной от клик.
Эрдёш использовал этот аргумент, чтобы доказать: если запретить красные и синие клики размера k, то число Рамсея R(k) должно быть больше √2 k. Числа Рамсея для красных и синих клик одинакового размера называются диагональными числами Рамсея. Эрдёш смог аналогичным образом получить нижнюю границу для «внедиагональных» чисел Рамсея R(k, l), при которых запрещены красные клики размера k и синие клики размера l.
Доказательство состояло всего из нескольких строк. Но оно было совершенно неожиданным.
Сначала математики не хотели его принимать. Им нужны были конкретные примеры. «На протяжении многих лет Эрдёш был голосом в пустыне, — сказал Спенсер. — Он получал эти поразительные результаты, используя случайность, а до него никто так не делал».
Но вскоре вероятностный метод доказал свою ценность. Сейчас это один из самых распространённых методов в «дискретной» математике — науке, изучающей объекты (такие как графы), которые являются дискретными, а не непрерывными. И этот метод проник из математики в физику и информатику. «Случайность, на мой взгляд, просто помогает нам понять то, что иначе было бы очень абстрактным», — сказал Хорн.
Совсем недавно математики смогли адаптировать метод Эрдёша для получения более точных оценок чисел Рамсея, в которых запрещённые клики значительно различаются по размеру. Например, в 2025 году Хорн и трое его коллег использовали обновлённую версию метода Эрдёша, чтобы доказать более точную нижнюю границу для R(3, l), где l становится произвольно большим. (Эта работа, в свою очередь, привела к значительному прорыву в теории графов).
Но когда речь шла о числах Рамсея, в которых запрещённые клики не так сильно различались по размеру — особенно о диагональных числах Рамсея, которые изначально интересовали Эрдёша, — вероятностный метод зашёл в тупик. Допустим, вы запрещаете клики размером 1000. Эрдёш показал, что R(1000) должно быть больше примерно 2500. Восемь десятилетий усилий позволили изменить эту границу до примерно 2501. Аналогичным образом, начиная с 1970-х годов прогресс в исследовании внедиагональных чисел Рамсея, где запрещённые красные и синие клики являются относительно большими, оставался на месте.
И вот появился аспирант, практически не имевший опыта работы с теорией Рамсея.
Коррелированное раскрашивание
Вуцзе Шэнь провёл свои первые несколько семестров в Университете Цинхуа, уделяя основное внимание геометрии и топологии. Но весной 2024 года он наткнулся на статью о числах Рамсея, которая его увлекла.
Он знал, как работает метод Эрдёша: нужно подбрасывать монету, чтобы определить цвет каждого ребра графа: «орёл» — ребро красное; «решка» — синее. Затем вычисляется вероятность получения раскраски без клик. Но для больших графов этот расчёт становится очень сложным. Шэнь задался вопросом, существует ли случайная модель, которая могла бы генерировать раскраски без клик более эффективно, чем подход Эрдёша.
Учитывая образование Шэня, пожалуй, неудивительно, что разработанная им модель связана с геометрией. Обычно при раскрашивании графов к геометрии не прибегают: для математиков важно лишь то, какие вершины соединены красным ребром, а какие — синим. Расположены ли эти вершины близко друг к другу или разбросаны по всему пространству, не имеет никакого значения.
Но Шэнь хотел использовать геометрию, чтобы определить, какие рёбра окрашивать в красный цвет, а какие — в синий. В частности, он хотел использовать геометрию многомерных сфер — то есть множеств точек, равноудалённых от одной центральной точки.
Эти сферы «полностью переворачивают все наши интуитивные представления», — сказал Дэвид Конлон из Калифорнийского технологического института. Многие из наших представлений о том, как выглядит сфера, в высоких измерениях уже не верны: многомерная сфера имеет крошечный объём и огромную площадь поверхности, а большинство её точек лежит на экваторе. «Работать с ней довольно сложно», — отметил Судаков.
Но Шэнь и двое его коллег — Цзе Ма, который приезжал в Цинхуа для преподавания в осеннем семестре, и аспирант Ма Шэнцзе Се — решили попробовать. Их метод заключался в следующем: сначала поочерёдно разместить узлы на поверхности многомерной сферы. Положение каждого узла выбирается случайным образом — любая точка на сфере подходит, и расположение одного узла никак не влияет на расположение других узлов.
После того как вы разместили все узлы, раскрасьте каждое ребро в зависимости от расстояния между узлами. Если расстояние между двумя точками превышает некоторое фиксированное значение (что будет происходить с вероятностью менее 1/2), раскрасьте соединяющее их ребро в красный цвет. Если они находятся ближе друг к другу, раскрасьте ребро в синий цвет.
Благодаря этому подходу графы, созданные Ма, Шэнем и Се, с меньшей вероятностью образовывали красную клику. Это объясняется тем, что для образования большой красной клики требуется много узлов, расположенных на большом расстоянии друг от друга. Учитывая ограниченное пространство на сфере, такое развитие событий маловероятно.
Но есть одна загвоздка. По той же причине этот метод также генерирует больше раскрасок с синими кликами, чем метод Эрдёша. «Существует компромисс, который, похоже, действительно помогает в одном случае, но совершенно не помогает в другом, — сказал Конлон. — Зачем тогда вообще этим заниматься?»
Несмотря на это, Ма, Шэнь и Се были полны надежды. Они протестировали свой метод на графах меньшего размера, и он, казалось, работал: среди десятков тысяч плохих раскрасок, которые он генерировал, всё же оставалась ненулевая вероятность получить и хорошую раскраску без клик. Это убедило их в том, что преимущества могут перевесить издержки даже для гораздо более крупных графов.
Затем они приступили к доказательству этой гипотезы. Ключом к решению оказалась весьма необычная геометрия многомерных сфер.
В конечном итоге, чтобы показать, что им удаётся избежать появления клик определённого размера, Ма, Шэнь и Се должны были ограничить вероятность того, что их случайно размещённые узлы образуют кластеры, которые либо все находятся далеко друг от друга, либо все — близко друг к другу. Они поняли, что если провести линии от каждого узла к центру сферы, то почти все эти линии будут перпендикулярными или близкими к перпендикуляру. Такого не происходит, если случайным образом размещать узлы на привычной двумерной сфере: большинство узлов не будут лежать на перпендикулярных линиях. Но команда смогла доказать, что это верно в гораздо более высоких измерениях, с которыми они работали.
Это, в свою очередь, ограничивало расстояние, на котором узлы могли находиться друг от друга, тем самым снижая вероятность образования одноцветной клики.
Спустя год и после 40 страниц сложных вычислений в июле 2025 года трое учёных опубликовали свою статью. Им удалось улучшить нижнюю границу Эрдёша для чисел Рамсея — но только в том случае, когда запрещённые синие клики больше красных. Когда синие клики столь же малы, как и красные, преимущества нового подхода исчезают.
Тем не менее, если нужно избежать красных клик, которые, скажем, в два раза меньше синих, Ма, Шэнь и Се сумели повысить показатель роста Эрдёша с ((√5+1)/2) k до ((√5+1)/2+10−21) k. Хотя изменение и незначительно, их доказательство стало первым улучшением результатов для почти диагональных чисел Рамсея за последние 50 лет.
«Это удача, и мы чувствуем, что все наши усилия вознаграждены, — сказал Ма. — Но долгое время было очень тяжело».
«Удивительно, что знакомый подход работает для решения знакомой задачи», — отметил Джулиан Сахасрабудхе из Кембриджского университета. По его словам, их метод «был у всех на виду, но оставался незамеченным».
«Вероятностная игровая площадка»
Доказательство Ма, Шэня и Се уже привело к целой череде дальнейших достижений. В декабре 2025 года Судаков и двое его аспирантов радикально упростили модель раскрашивания, ещё больше улучшив установленные ими новые границы. С тех пор другие исследователи использовали эту модель для оценки чисел Рамсея, в которых задействованы три цвета, а не два.
Это вполне соответствует долгой истории вероятностного метода. На протяжении последних 80 лет математики экспериментировали с методом Эрдёша, основанным на случайности, находя всё новые и новые способы вводить дополнительную структуру для повышения его эффективности. Неизбежно, что эти новые методы впоследствии оказались полезными и в других областях. «Это очень плодотворная площадка для идей», — сказал Судаков.
Таким образом, работа Ма, Шэня и Се является новейшей главой в этой многолетней истории. Но это также первая за долгое время работа, в которой вновь рассматриваются почти диагональные числа Рамсея.
Новый вклад команды — геометрический подход — может привести к дальнейшему прогрессу в решении этой упорной проблемы. Хотя вероятностный метод ещё не доведён до совершенства, «сейчас он реально очень мощный», — сказал Спенсер. «Он сильно изменился».
