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