Дэвид Конлон и Асаф Фербер повысили нижнюю границу для многоцветных «чисел Рамсея», которые количественно определяют, насколько большими могут стать графы, прежде чем закономерности неизбежно проявятся. Сохранить статью Прочитать позже
Введение
После более чем 70 лет упорства одно из самых неподатливых чисел в математике наконец-то сдвинулось с места.
В четырехстраничном доказательстве, опубликованном в конце сентября, Дэвид Конлон и Асаф Фербер представили самую точную на сегодняшний день оценку для «многоцветных чисел Рамсея», которые измеряют, насколько большими могут стать графы, прежде чем в них неизбежно появятся определенные виды закономерностей.
«В этой Вселенной нет абсолютной случайности», — сказала Мария Аксенович из Технологического института Карлсруэ в Германии. «Всегда существуют кластеры порядка, и числа Рамсея количественно его характеризуют».
Графы представляют собой наборы точек (вершин), соединённых линиями (рёбрами). Математиков особенно интересует, сколько вершин и рёбер они могут содержать, прежде чем внутри них возникнут различные типы подструктур.
«Если у вас достаточно большой граф, то значительная его часть очень строго упорядочена», — сказала Мария Чудновская из Принстонского университета. «Сложно объяснить, почему что-то красиво, но все согласны с тем, что это прекрасное явление».
Числа Рамсея относятся к определенному шаблону, называемому монохроматической кликой, представляющему собой набор вершин, соединенных друг с другом ребрами одного цвета после выполнения определенной процедуры раскраски.
Числа Рамсея различаются в зависимости от размера искомой клики и количества цветов, используемых для раскраски. Математики не могут вычислить большинство чисел Рамсея, поскольку все графы, кроме самых маленьких, слишком сложны для прямого анализа.
Обычно лучшее, что могут сделать математики, — это установить диапазон возможных значений чисел Рамсея. Это как если бы вы хотели узнать местонахождение друга, но могли бы с уверенностью сказать только, что он находится к северу от Майами и к югу от Филадельфии.
Новое доказательство делает больше для точного определения чисел Рамсея, чем любой другой результат с тех пор, как Пол Эрдёш впервые изучил их в 1930-х и 1940-х годах. Конлон из Калифорнийского технологического института и Фербер из Калифорнийского университета в Ирвайне нашли новую «нижнюю границу» для многоцветных чисел Рамсея, которая экспоненциально точнее предыдущей наилучшей оценки. Их результат даёт математикам новое понимание взаимодействия порядка и случайности в графах, представляющих фундаментальный интерес для математики.
«Это фантастический результат, — сказал Аксенович. — Мне очень нравится».
Красочные связи
Числа Рамсея, введённые британским учёным-полиматом Фрэнком Рамсеем в 1920-х годах, лучше всего понять на примере. Начнём с графа с пятью вершинами. Соединим каждую из них со всеми остальными, чтобы получить то, что математики называют полным графом. Можно ли раскрасить каждое ребро в красный или синий цвет, не создавая при этом множества из трёх вершин, соединённых друг с другом рёбрами одного цвета? Ответ: можно.
Но начнём с полного графа из шести вершин, и теперь нет способа раскрасить рёбра двумя цветами, не создав одноцветную клику из как минимум трёх вершин. Или, другими словами, для двух цветов и клики размера 3 число Рамсея равно 6 (поскольку для этого требуется полный граф из шести вершин).
Числа Рамсея варьируются в зависимости от количества цветов и размера искомой одноцветной клики. Но, как правило, их сложно точно вычислить, и математики знают точные значения лишь для небольшого числа ситуаций. Даже для небольших клик размером 5 (и двух цветов) число Рамсея, по их словам, находится в пределах от 43 до 48.
«Это действительно стыдно», — сказал Юваль Вигдерсон, аспирант Стэнфордского университета. «Мы работаем над этой проблемой почти 100 лет и ничего не знаем».
Числа Рамсея сложно вычислить, поскольку сложность графа резко возрастает с добавлением вершин. Для графа с шестью вершинами и двумя цветами можно перебрать все возможные варианты вручную. Но для графа с 40 вершинами существует 2780 способов применения двух цветов.
«Слишком много всего нужно проверить», — сказал Аксенович.
Среди математиков, изучающих числа Рамсея, есть притча, обычно приписываемая Эрдёшу, которая иллюстрирует, как быстро эти вычисления становятся непреодолимыми. Однажды на планету вторгаются враждебные инопланетяне. Они предлагают пощадить планету, если мы сможем создать правильные числа Рамсея. Согласно притче, если они спросят число Рамсея для двухцветной клики размером 5, мы должны бросить все ресурсы человеческой цивилизации на его поиск. Но если они спросят для клики размером 6, мы должны быть готовы к битве.
«Если они попросят у нас число Рэмси 6, то забудьте об этом, мы начнем атаку», — сказал Аксенович.
Использование случайности
Поскольку вычислить точные числа Рамсея практически невозможно, математики вместо этого сосредотачиваются на них, доказывая, что они больше некоторой «нижней границы» и меньше некоторой «верхней границы». Новая работа повышает точность нижних границ, но не затрагивает верхние границы.
В 1935 году Эрдёш и Джордж Секереш установили первую такую границу. Они использовали краткое доказательство, чтобы показать, что двухцветные числа Рамсея должны быть меньше верхней границы 4t, где t — размер интересующей вас одноцветной клики. Они также обнаружили, что трёхцветные числа Рамсея должны быть меньше 27t. Десять лет спустя, в 1947 году, Эрдёш вычислил первые нижние границы для этих чисел: для двух цветов это ($latex sqrt{2}$)t вершин, а для трёх цветов — ($latex sqrt{3}$)t.
Между ($latex sqrt{2}$)t и 4t существует большая разница, особенно когда t становится очень большим. Эта разница отражает неточное понимание математиками чисел Рамсея. Но форма границ — то, как размер искомого графа выражается через размер искомой клики, — намекает на то, что математики больше всего хотят знать.
«Что нам действительно хотелось бы понять, так это динамику роста этих чисел [Рэмси] по мере увеличения размера клики», — сказала Лиза Зауэрманн, научный сотрудник Института перспективных исследований в Принстоне, штат Нью-Джерси.
По этой причине наиболее весомым вкладом Эрдёша в изучение чисел Рэмси стали не сами границы, а метод их вычисления. Вот что он сделал для нижней границы.
Представьте, что у вас есть полный граф с 10 вершинами и 45 рёбрами. И представьте, что вы хотите узнать, можно ли применить три цвета, не создавая одноцветную клику определённого размера, скажем, из пяти вершин (соединённых 10 рёбрами).
Можно начать, как это сделал Эрдёш, с случайного раскрашивания рёбер. Для каждого ребра бросьте эквивалент трёхгранной игральной кости и используйте выпавший цвет. Эрдёш знал, что вероятность того, что любое подмножество из 10 рёбер окажется одного цвета, легко вычислить. Это просто вероятность того, что одно ребро, скажем, красное, умноженная на вероятность того, что другое ребро тоже красное, и так далее для всех 10 рёбер (то есть 1/310). Затем он умножил это значение на 3, чтобы учесть тот факт, что существует три разных цвета, которые могут создать желаемую одноцветную клику.
Затем Эрдёш посмотрел на общее количество различных клик из пяти вершин в графе. Их 252. Наконец, он взял вероятность того, что одна из них создаст одноцветную клику, и добавил её к вероятностям того, что любая из остальных 251 вершин создаст эту клику. Это вычисление известно как «граница объединения» и оценивает вероятность создания одноцветной клики при случайной раскраске рёбер.
Пока граница объединения остаётся меньше 1, вы знаете, что метод случайной раскраски не гарантирует получение заданной одноцветной клики. В нашем примере граница объединения составляет 0,0128. Это означает, что вам далеко не гарантировано получение одноцветной клики из 5 вершин, а значит, число Рамсея для этого примера больше 10 вершин.
Математики называют этот подход вероятностным. Это остроумный способ обойти проблему, которая иначе была бы неразрешима. Вместо того, чтобы искать примеры раскрасок, не содержащих одноцветных клик разного размера, Эрдёш просто доказал, что такие раскраски без клик должны существовать (поскольку граница объединения меньше 1), то есть число Рамсея должно быть больше количества вершин в графе, который вы в данный момент раскрашиваете случайным образом.
«Мы можем доказать существование чего-либо, не демонстрируя, что это такое», — сказал Вигдерсон.
За последующие 70 лет математики улучшили нижнюю границу Эрдёша для двух и трёх цветов лишь однажды — в 1975 году, благодаря постепенному уточнению Джоэлом Спенсером. Многие работали над этой проблемой, но никто не смог найти лучшего способа вычисления чисел Рамсея, чем вероятностный метод. «Проблема заключалась в попытке обойти эту [границу], вытекающую из случайной выборки», — сказал Конлон.
И именно это Конлон и Фербер наконец сделали этой осенью.
Порядок включения
Новое доказательство улучшает нижнюю границу чисел Рамсея для трех и более цветов.
До работы Конлона и Фербера нижняя граница для трёх цветов составляла ($latex sqrt{3}$)t (приблизительно 1,73t). Они улучшили эту границу до 1,834t. Для четырёх цветов они подняли нижнюю границу с 2t до 2,135t. Оба результата представляют собой гигантский скачок. Увеличивая основание возводимого числа в степень t, Конлон и Фербер доказали, что существуют экспоненциально большие трёх- и четырёхцветные графы, не содержащие необходимых одноцветных клик. Другими словами, они показали, что беспорядок может сохраняться в графах большего размера, чем было известно ранее.
Целью Конлона и Фербера было раскрасить весь граф, не создавая больших одноцветных клик. Для этого они нашли способ эффективно распределить один цвет (красный) по фиксированному правилу, а затем случайным образом нанести остальные цвета. Этот гибридный метод дал им дополнительный контроль над структурой графа, которого не было у Эрдёша.
Для фиксированной части плана они поместили вершины в особое геометрическое пространство, так что каждая вершина определялась набором координат. Затем они решили, какие рёбра окрашивать в красный цвет, с помощью двухэтапного процесса.
Сначала они взяли координаты каждой вершины, возвели их в квадрат и сложили — процесс, известный как взятие суммы квадратов. В силу природы этого конкретного геометрического пространства эта операция суммирования квадратов давала одно из двух значений: 0 или 1. Затем, сосредоточившись только на вершинах, сумма квадратов которых была равна 0, они вычислили «внутреннее произведение» между парами вершин — стандартную операцию в линейной алгебре. Если ребро соединяло пару вершин, чьё внутреннее произведение было определённым значением, они окрашивали его в красный цвет. Это составляло половину общего числа рёбер.
Завершив эту детерминированную часть своего подхода, Конлон и Фербер перешли к случайной части. Для оставшихся рёбер они подбрасывали монетку — как это сделал бы Эрдёш — чтобы определить, в какой цвет покрасить данное ребро: синий или зелёный.
Этот подход оказался отличным способом избежать образования одноцветных клик по мере роста размера графа. Это было сделано намеренно: пара разработала детерминированный шаг для генерации красных рёбер, разбросанных по всему графу. На расстоянии они выглядели почти как разбросанные случайным образом — и действительно, Конлон и Фербер называют такое расположение красных рёбер «псевдослучайным».
Такое псевдослучайное распределение красных рёбер позволяет достичь двух желаемых результатов. Во-первых, разбрасывая красные рёбра, мы гарантируем отсутствие крупных красных клик (чего мы и пытаемся избежать, если хотим увеличить нижнюю границу). Во-вторых, распределённые красные рёбра разбивают граф, оставляя меньше свободных пространств, которые могли бы случайно заполниться одноцветными кликами другого цвета.
«Мы хотели убедиться, что первый цвет, который мы использовали детерминированно, уменьшил количество потенциальных клик», — сказал Фербер.
Математики быстро отреагировали на новое доказательство. Через несколько дней после его публикации Вигдерсон опубликовал следующую статью, в которой, используя их методы, доказал ещё более точную нижнюю границу для чисел Рамсея для четырёх и более цветов. После десятилетий застоя в изучении чисел Рамсея плотина наконец прорвалась.
«Наши знания зашли в тупик со времен Эрдёша в 40-х годах, поэтому все, что предлагает новый подход к вопросам такого типа, является захватывающим», — сказал Вигдерсон.
Исправление: 9 ноября 2020 г.
Некоторые версии нашей диаграммы по «Метод Эрдёша» описывали граф с 0 вершинами; должно быть 10. Теперь все версии верны.
Источник: www.quantamagazine.org
