Числа рамсея

Давид Конлон и Асаф Фербер подняли нижнюю границу для значений многоцветных чисел Рамсея. Эти числа говорят о том, насколько можно увеличивать граф, пока в нём не начнут появляться неизбежные закономерности

Одни из самых упрямых чисел математики, после более 70 лет сопротивления, наконец, начинают поддаваться.

В опубликованном в сентябре четырёхстраничном доказательстве Давид Конлон и Асаф Фербер дали наиболее точную оценку многоцветным числам Рамсея. Эти числа описывают размер графов, до которого они могут вырасти перед тем, как в них начнут неизбежно проявляться определённые закономерности.

В нашей Вселенной абсолютных случайностей нет, сказала Мария Аксенович из Технологического института Карлсруэ в Германии. Всегда где-то есть скопления порядка, и числа Рамсея оценивают его количественно.

Графы это наборы точек (вершин), соединённых линиями (рёбрами). Особенно математиков интересует вопрос, сколько вершин и рёбер можно добавить в граф перед тем, как в нём начнут появляться различные подструктуры.

Если ваш граф достаточно большой, то значительная его часть будет хорошо упорядочена, сказала Мария Чудновски из Принстонского университета. Красоту сложно объяснить словами, однако это явление принято считать красивым.

Числа Рамсея относятся к определённой последовательности, монохромной клике. Это набор вершин, которые будут соединены друг с другом рёбрами одного и того же цвета после определенной процедуры раскрашивания.


Асаф Фербер из Калифорнийского университета в Ирвине

Числа Рамсея разнятся в зависимости от размера искомой клики и количества цветов, в которые вы раскрашиваете граф. Большую часть чисел Рамсея математики подсчитать не могут, поскольку почти все графы, кроме самых простых, оказывается слишком сложно анализировать напрямую.

Лучшее, на что обычно способны математики задать диапазон возможных значений чисел Рамсея. Как если бы вы хотели узнать, где находится в данный момент ваш друг, но всё, что вам удалось установить это что он где-то южнее Москвы и севернее Сочи.

Новое доказательство позволяет определить диапазон значений чисел Рамсея гораздо точнее любого результата с тех пор, как эти числа впервые начал изучать Пал Эрдёш в 1930-х и 40-х годах. Конлон из Калифорнийского технологического института и Фербер из Калифорнийского университета в Ирвине обнаружили новую нижнюю границу для многоцветных чисел Рамсея. Она получилась экспоненциально более точная, чем лучшая из предыдущих оценок. Их результат даёт математикам новый способ понять имеющую чрезвычайную важность для них схему взаимодействия порядка и случайности в графах.

Это потрясающий результат, сказала Аксенович. Мне он очень понравился.

Цветные связи

Суть чисел Рамсея, придуманных британским учёным-универсалистом Фрэнк Рамсей в 1920-х, проще всего понять на примере. Начнём с графа, состоящего из пяти вершин. Соединим каждую вершину со всеми остальными получится, как говорят математики, полный граф. Можно ли раскрасить все рёбра в синий или красный цвет так, чтобы в графе не нашлось трёх вершин, соединённых друг с другом попарно рёбрами одного цвета? В данном случае да.

Но если мы начнём с полного графа из шести вершин, раскрасить его рёбра двумя цветами, не порождая монохромную клику из трёх или более вершин, не получится. Иначе говоря, для двух цветов и размера клики 3 число Рамсея будет равным 6 (в графе должно быть не менее 6 вершин).

Числа Рамсея меняются в зависимости от количества цветов и размера искомой монохромной клики. Но в целом их сложно вычислять точные значения известны математикам только в небольшом числе случаев. Даже для небольших клик размером 5 и двух цветов лучше, что могут сказать математики по поводу числа Рамсея что оно находится в промежутке от 43 до 48.

Неловкая ситуация, сказал Ювал Уигдерсон, аспирант из Стэнфорда. Мы работаем над этой задачей уже почти 100 лет, и так ничего и не узнали.


Соедините пять вершин, сформировав полный граф. Такой граф можно раскрасить двумя цветами так, чтобы не появилось трёх вершин, соединённых рёбрами одного цвета.
Но перейдя к графу из шести вершин, уже невозможно избежать появления трёх таких вершин.

Числа Рамсея сложно подсчитать потому, что сложность графа быстро растёт с ростом количества вершин. Для графа из шести вершин и двух цветов все варианты можно перебрать вручную. Для графа из 40 вершин существует 2780 способов раскрасить рёбра в два цвета.

Приходится проверять слишком много, сказала Аксенович.

У математиков, изучающих числа Рамсея, есть байка, создание которой обычно приписывают Эрдёшу. Она описывает, насколько быстро эти вычисления становятся слишком сложными. Представьте, что на Землю вторглись инопланетяне. Они предлагают пощадить нашу планету, если мы сможем выдать правильные значения чисел Рамсея. Если они попросят нас назвать число Рамсея для случая с двумя цветами и кликами размера 5, нам нужно будет бросить все ресурсы человечества на решение этой задачи. Если же они попросят нас посчитать число Рамсея для клик размера 6, нам проще будет сразу готовиться к сражению.

Если они попросят у нас число Рамсея для [клик размера] 6, то лучше сразу атаковать, сказала Аксенович.

Изучая случайность

Поскольку подсчитать точное значение чисел Рамсея, по большому счёту, невозможно, математики вместо этого предпочитают постепенно ограничивать их значения. Они доказывают, что число больше некоего нижнего предела, и меньше верхнего предела. Новая работа улучшает эту точность для нижних пределов, но ничего не говорит о верхних.

В 1935 году Пал Эрдёш и Дьёрдь Секереш установили первую такую границу. Они применили короткое доказательство того, что числа Рамсея для двух цветов должны быть меньше, чем 4^t, где t размер интересующей вас монохромной клики. Они также обнаружили, что числа Рамсея для трёх цветов должны быть меньше 27^t. Через 10 лет, в 1947 году, Эрдёш подсчитал первую нижнюю границу для этих чисел: для двух цветов это (2)^t вершин, а для трёх (3)^t.

Между (2)^t и 4^t есть большая разница, особенно при очень больших значениях t. Этот разрыв отражает нечёткое понимание чисел Рамсея математиками. Однако форма границ то, как размер нужного графа выражается через размер нужной клики намекает на то, что больше всего интересно математикам.

Что мне очень хотелось бы понять это то, как растут эти числа Рамсея с ростом размера клики, сказала Лиза Сауэрман, постдок в Институте передовых исследований в Принстоне.

Поэтому самым долгоживущим вкладом Эрдёша в изучение чисел Рамсея оказались не сами границы, а метод их подсчёта. Вот, как он считал нижнюю границу.

Представьте, что у вас есть полный граф с 10 вершинами и 45 рёбрами. Представьте, что вам нужно узнать, возможно ли раскрасить рёбра тремя цветами, не создавая монохромную клику определённого размера допустим, 5 (5 вершин, соединённых 10 рёбрами).

Можно начать, как сделал Эрдёш, со случайного раскрашивания рёбер. Для каждого ребра бросим что-то вроде трёхгранного кубика и раскрасим тем цветом, который выпадет случайно. Эрдёш знал, что легко подсчитать вероятность того, что любое подмножество из 10 рёбер окажется одного цвета. Нужно просто перемножить вероятность того, что одно из рёбер будет, допустим, красным, с вероятностью того, что другое ребро будет красным, и так далее для всех десяти рёбер (то есть, 1/3¹⁰). Затем он умножил то число на три, чтобы учесть тот факт, что нужную монохромную клику может породить любой из трёх разных цветов.

Потом Эрдёш посмотрел на общее количество разных клик из пяти вершин в графе. Всего их может быть 252. Наконец, он взял вероятность того, что одна из них выдаст монохромную клику, и добавил её к вероятностям того, что любая из оставшихся 251 вершины выдаст такую клику. Это т.н. подсчёт границы объединения, который даёт вероятность получения монохромной клики при случайном раскрашивании рёбер.

Пока граница объединения остаётся меньше 1, вы знаете, что метод случайной раскраски не гарантирует появления заданной монохромной клики. В нашем примере граница равна 0,0128. Это очень далеко от гарантированного появления монохромной клики в 5 вершин, а значит, для данного примера число Рамсея больше 10 вершин.

Математики называют такой подход вероятностным методом. Это гениальный обходной манёвр для решения трудных задач. Вместо того, чтобы искать примеры раскрасок, не содержащие монохромных клик различных размеров, Эрдёш просто доказал, что такие бескликовые раскраски должны существовать (поскольку граница объединения меньше 1). То есть, число Рамсея должно быть больше количества вершин графа, который мы раскрашиваем случайным образом.


Пал Эрдёш изобрёл вероятностный метод подсчёта чисел Рамсея.
1) Начинаем с полного графа из 10 вершин. При раскраске рёбер тремя цветами всегда ли можно найти 5 вершин, соединённых 10 рёбрами одного цвета?
2) Вероятность того, что конкретное ребро красное (а не синее или жёлтое) равна 1/3
3) Вероятность того, что 10 рёбер красные, равна (1/3)¹⁰
4) Всего монохромную клику могут породить три цвета.
5) Общее количество разных клик из 5 вершин равно 252.
(1/3)¹⁰ * 3 * 252 = 0,0128 вероятность получить монохромную клику при случайной раскраске рёбер.

Мы можем доказать существование чего-то, не демонстрируя его напрямую, сказал Уигдерсон.

В последовавшие 70 лет математики улучшили нижнюю границу Эрдёша для двух и трёх цветов всего однажды в 1975 году инкрементальное её улучшение провёл Джоэл Спенсер. Многие работали над этой задачей, но никому не удалось найти способа для подсчёта чисел Рамсея лучше, чем вероятностный метод. Проблема заключалась в том, чтобы попытаться обойти это [ограничение], возникающее из-за случайной выборки, сказал Конлон.

Именно это и удалось сделать Конлону и Ферберу этой осенью.

Включение порядка

Новое доказательство улучшает нижнюю границу чисел Рамсея для трёх и более цветов.

До этой работы нижняя граница для трёх цветов равнялась (3)^t (примерно 1,73 ^t). Конлон и Фербер улучшили её до 1,834^t. Для четырёх цветов они подняли нижнюю границу с 2^t до 2,135^t. Оба эти результата гигантские шаги вперёд. Увеличивая основание, возводимое в степень t, Конлон и Фербер доказали существование экспоненциально больших графов, раскрашенных в три и четыре цвета, у которых нет монохромных клик. Иначе говоря, показали, что беспорядок встречается в более крупных графах, чем считалось ранее.

Целью Конлона и Фербера было раскрасить полный граф, не создавая крупные монохромные клики. Они придумали для этого способ эффективного распределения одного цвета (допустим, красного) по фиксированному правилу перед тем, как применять все остальные цвета случайным образом. Этот гибридный метод дал им контроль над структурой графа, которым не обладал Эрдёш.


Давид Конлон из Калифорнийского технологического института

Фиксированное правило подразумевало распределение вершин в особом геометрическом пространстве, в котором каждая из вершин определялась набором координат. Потом они применяли двухэтапный процесс, решая, какие рёбра красить в красный цвет.

Сначала они брали координаты каждой вершины, возводили их в квадрат и складывали, получая сумму квадратов. Из-за особенности этого геометрического пространства сумма квадратов давала одну из двух величин, 0 или 1. Затем они оставляли только те вершины, чья сумма давала 0, и подсчитывали скалярное произведение пар вершин (стандартная операция для линейной алгебры). Потом они окрашивали ребро в красный, если оно соединяло пару вершин, скалярное произведение которых равнялось определённой величине.

Завершив детерминистскую часть алгоритма, Конлон и Фербер переходили к случайной. Для всех остальных рёбер они подбрасывали монетку как делал бы Эрдёш чтобы определить, будет ли оно зелёным или синим.

Этот подход оказался прекрасным способом избегать появления монохромных клик с ростом графа. Так и было задумано: парочка специально разработала детерминистский этап так, чтобы красные рёбра равномерно распределялись по всему графу. На первый взгляд они выглядели так, будто распределялись случайным образом. В самом деле, Конлон и Фербер называют эту раскраску рёбер псевдослучайной.

Псевдослучайное распределение красных рёбер достигает двух целей. Первая: разбрасывая красные рёбра по всему графу, мы гарантируем, что в нём не появятся большие красные клики (именно этого мы пытаемся избежать, желая увеличить нижнюю границу). Вторая: разбросанные по всему графу красные рёбра разбивают его на части, оставляя меньше пустых мест, которые случайно могли бы заполнить монохромные клики другого цвета.

Мы хотели убедиться, что первый цвет, который мы использовали детерминистически, уменьшал количество потенциальных клик, сказал Фербер.

Математики быстро отреагировали на новое доказательство. Уже через несколько дней после выхода Уигдерсон опубликовал следующую за этой работу, где их метод использовался для ещё одного повышения нижней границы чисел Рамсея для случая с четырьмя и более цветами. После десятилетий неподвижности, плотина чисел Рамсея была, наконец, прорвана.

Наши знания по этой теме не менялись с 40-х годов, со времён Эрдёша. Поэтому всё, что даёт нам новый подход к подобного типа вопросам, вызывает живой интерес, сказал Уигдерсон.

Ашвин Сах возрастом в 21 год выдал несколько научных работ, которые опытные математики посчитали беспрецедентными для студента колледжа

19 мая Ашвин Сах опубликовал лучший на сегодня результат в одной из самых важных областей комбинаторики. В такой момент иной человек поднял бы бокал в честь данного события, однако Сах тогда был ещё недостаточно взрослым для того, чтобы пить алкоголь [по законам США / прим. пер.].

Это доказательство стало очередной работой из целого списка математических достижений, которые Сах, отпраздновавший свой 21-й день рождения в ноябре, опубликовал во время своей учёбы в Массачусетском технологическом институте. Данная работа была опубликована сразу после того, как он получил учёную степень. Это редкий случай такого раннего развития даже для области знаний, в которой появляется достаточно много молодых гениев.

Будучи студентом, он опубликовал достаточно работ для того, чтобы его можно было принимать на работу в университет, сказал Дэвид Конлон из Калифорнийского технологического института.

Майское доказательство касалось важной особенности комбинаторики, чисел Рамсея. Они количественно описывают размер графа (набора точек, или вершин, связанных рёбрами), до которого он может дорасти, пока в нём неизбежно не начнут возникать определённые закономерности.

Представьте, к примеру, что у вас есть шесть вершин, попарно соединённых друг с другом рёбрами. Раскрасьте каждое из 15 рёбер в синий или красный цвет. Неважно, как вы будете использовать цвета вы неизбежно получите три вершины, связанные друг с другом рёбрами одного цвета (это будет т.н. клика). Однако если начать с пяти вершин, это уже будет не так такой граф можно раскрасить, не сформировав клику. В итоге, как говорят математики, число Рамсея для двух цветов и клики размера 3 равняется 6 то есть, чтобы гарантировать существование такой клики, вам нужно не менее 6 вершин.

С ростом размера клик точные числа Рамсея становится очень сложно вычислять. Математики пытаются вместо этого оценить их величину, давая гарантии, что число Рамсея для клики любого размера будет большим, чем некое число (это будет нижняя граница), и меньше, чем другое число (верхняя граница).

Пал Эрдёш и Дьёрдь Секереш начали исследования нижних и верхних границ чисел Рамсея в 1930-х годах. С тех пор математики с ними почти не продвинулись хотя недавно мы уже писали об инновационном доказательстве, задавшем лучший на сегодня нижний предел для чисел Рамсея.


В мае Ашвин Сах показал, насколько может вырасти граф до тех пор, пока в нём неизбежно не появятся определённые закономерности, отодвинув тем самым границы достигнутого в этой области.

Доказательство Саха наоборот, улучшило верхнюю границу для чисел Рамсея для двух цветов. Сделал он это через оптимизацию метода, придуманного самими Эрдёшем и Секерешем. Мало какие математики смогли улучшить его с момента его изобретения. Результат Саха доказывает, что при достижении графом определённого размера в нём неизбежно начнут появляться клики некоего соответствующего размера. Многие математики считают, что этот результат при текущем состоянии знаний в данной области улучшить уже невозможно.

Он довёл этот метод до логического максимума, сказал Конлон, автор предыдущей лучшей оценки верхнего предела для этой задачи.

Жизнь в математике

Сах вырос в Портленде, Орегон, и ему с детства нравилась математика. Некоторые из моих самых ранних воспоминаний связаны с тем, как мама учит меня основам арифметики, сказал он.

Впервые он почувствовал вкус к математике на соревнованиях, где часто побеждал. Летом 2016 года, когда ему было 16, он завоевал золотую медаль на международной математической олимпиаде в Гонконге. В следующем году он поступил в MIT (и через два с половиной года получил диплом).

Среди установленных там контактов два стали самыми важными для его математического развития. Первым был профессор Юфей Жао. В первый год Сах записался к нему сразу на два курса, одним из которых была комбинаторика. Сах выделялся даже среди самых талантливых студентов мира, изучавших математику.


11-летний Сах

Он явно в совершенстве владел материалом, хотя был всего на первом курсе, сказал Жао.

Вторым стал Мехтааб Соуни, которому сейчас 22 года. Соуни учился на год старше Саха, и той осенью перевёлся в MIT из Пенсильванского университета. В сентябре они встретились в классе и подружились.

К весне они уже вместе работали над исследованием. Они работали над различными темами из области дискретной математики, в частности, над теорией графов, теорией вероятности и свойствами случайных матриц. Многие из изучаемых ими задач было довольно просто сформулировать и решать напрямую для них не требовалось многолетнего формального образования и исследований.

Мне нравятся задачки, которые можно обдумывать с использованием базовых принципов, чтобы не нужно было читать огромные горы литературы или иметь обширные теоретические знания, сказал Соуни.

Они плотно работали с Жао, предлагавшим им вопросы для изучения и объяснявшим, как писать формальные работы по математике. Часто Жао предлагал им разобраться в определённое задаче, надеясь, что она займёт их на какое-то время однако они возвращались с ответом уже на следующий день.



Сах работает в парке

Оба они невероятно энергичные. Я кидаю им вопрос и почти сразу получаю ответ, сказал Жао.

За последние три года Сах и Соуни написали уже несколько десятков работ, и многие из них в соавторстве. Этой осенью они победили в конкурсе на приз Моргана, который в США, Канаде и Мексике дают лучшим математикам-студентам. Жао отметил, что их совместные достижения беспрецедентны.

Традиция студенческих исследований существует давно, но не на таком уровне качества и количества, какое наблюдается у Ашвина и Мехтааба, сказал он.

Сах и Соуни сейчас уже аспиранты MIT, хотя из-за пандемии они временно находятся на противоположных побережьях. Сах вернулся в Портленд, а Соуни живёт на Лонг-Айленде в Нью-Йорке, где он вырос. Однако они всё равно постоянно на связи.

Мы созваниваемся раз-два в день, и общаемся по 5-6 часов, сказал Соуни. А когда не встречаемся, постоянно обмениваемся сообщениями.

Они говорят, что их ранние успехи на них не давят. Даже наоборот, мотивируют их на новые свершения.

Я стараюсь не зацикливаться на прошлом, говорит Сах. Я всегда смотрю вперёд, на то, что могу сделать в будущем.