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