Как математики сдвинули с мертвой точки диагональное число Рамсея
В комбинаторике прямо сейчас происходит много весьма интересных событий, это одна из самых бурно развивающихся областей математики. Но среди них отдельно выделяется новая работа Марсело Кампоса, Саймона Гриффитса, Роберта Морриса (Рио-де-Жанейро) и Джулиана Сахасрабуде (Кембридж), посвященная оценке чисел Рамсея. В чем с этими числами проблема и как ее недавно решили, рассказывает математик Фёдор Петров, профессор СПбГУ и ведущий научный сотрудник ПОМИ РАН.
Чтобы определить числа Рамсея, начнем с задачи, которую решают на школьных математических кружках: докажите, что из любых шести людей найдутся трое попарно знакомых или трое попарно незнакомых (будем считать, что знакомство взаимно).
Возьмем любого из шестерых — назовем его Иваном. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с Иваном, если нет — то тройку попарно незнакомых между собой. Если же Иван знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединенные ребрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это доказал английский математик Фрэнк Пламптон Рамсей в 1930 году. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n,k) и называется числом Рамсея. Выше мы установили, что R(3,3) = 6.
Считать числа Рамсея очень трудно. Известно, что:
А вот R(5,5) уже неизвестно. Известно только, что 43 ⩽ R(5,5) ⩽ 48.
Как говорил математик Пол Эрдёш больше 30 лет назад, если на Землю нападут пришельцы и потребуют в течение года назвать R(5,5) — а не то они тут все разнесут — то ценой максимального напряжения интеллектуальных сил и мощных компьютеров с этим можно справиться. Но если им понадобится R(6,6), то надо атаковать их превентивно. Положение с тех пор не изменилось.
Математиков часто интересуют даже не точные ответы, а асимптотические оценки: поведение при больших значениях параметра. Что же известно про поведение чисел Рамсея?
С одной стороны, есть неравенство R(n,k) ⩽ R(n,k − 1) + R(n − 1,k), которое доказывается аналогично приведенному выше рассуждению для R(3,3). Теперь у Ивана есть либо R(n,k − 1) знакомых, либо R(n − 1,k) незнакомых людей. А уже из этого неравенства выводится, что R(n,k) < 2n + k (достаточно заметить, что 2n + (k − 1) + 2(n − 1) + k = 2 × 2n + k − 1 = 2n + k, и применить индукцию).
Если сосредоточиться на диагональных числах Рамсея, то есть на случае n = k, получаем R(n,n) < 4n.
С другой стороны, существует оценка снизу: R(n,n) > 2n/2. Она получается с помощью вероятностного метода Эрдёша. А именно, допустим, что для каждой пары людей то, знакомы они или нет, определяется подкидыванием монетки — то есть они оказываются знакомы с вероятностью ½, причем для каждой пары монетка подкидывается отдельно. Тогда вероятность, что в группе размером не больше 2n/2 не найдутся ни n знакомых, ни n незнакомых пар, положительна — а значит, хотя бы один пример такой конфигурации знакомств существует.
Поэтому величина R(n,n) заключена между двумя экспонентами:
(√2)n < R(n,n) < 4n.
А можно ли улучшить одну из этих констант — √2 или 4 — так, чтобы неравенство по-прежнему было верно при всех достаточно больших n? На протяжении десятилетий эта задача считалась одной из самых важных в комбинаторике. Не столько из-за важности чисел Рамсея самих по себе (хотя и у них много приложений), сколько как вопрос, проверяющий меру нашего понимания больших комбинаторных структур, — подобно тому как Великая теорема Ферма долгое время проверяла наше понимание арифметики.
С нижней оценкой уже давно нет никаких сколько-то серьезных продвижений, а по верхней около 15 лет назад появилась работа Дэвида Конлона, который смог поделить 4n на функцию, растущую быстрее любого многочлена, но медленнее экспоненты.
И вот в новой работе содержится доказательство тому, что верхнее ограничение можно уменьшить. При этом авторы не стремились оптимизировать свой метод так, чтобы получить как можно лучшую константу, — а значит можно не сомневаться, что множество людей сейчас этим займутся.
Работа не короткая, но ясно написанная и весьма элементарная в математическом значении этого слова — не использующая понятий, выходящих за рамки обсуждаемого вопроса. Многие математики уже проверили доказательство, вопросов к нему нет.
Предыдущие улучшения верхних оценок чисел Рамсея — в работах Томассена, а затем Конлона и Саха — основывались на идее так называемой квазислучайностиКвазислучайным называют объект, ведущий себя как случайный, но полученный не в результате случайного выбора. Например, десятичные цифры числа π распределены, видимо, квазислучайно в любом разумном смысле. В нашем случае речь о квазислучайных графах.. Подход в новой работе совершенно другой. Но в ней используется понятие книги, которое ввели их предшественники.
Книга знакомств — это пара непересекающихся множеств S иT в нашей компании, в которой люди из S знакомы и друг с другом, и со всеми из T. Аналогично определяется и книга незнакомств.
Авторы берут любую компанию, в которой есть хотя бы 3,9999n людей, и начинают искать в ней n знакомых (или незнакомых) людей. Для этого они последовательно выделяют в ней подмножества A, B, X, Y, удовлетворяющие некоторым условиям, обобщающим понятие книги:
При этом авторы также отслеживают величину p — долю знакомых среди тех, где один человек из X, а второй из Y.
Они начинают с пустых A и B: в этом случае на множества X и Y условия выше не накладывают никаких требований, кроме того, что они не пересекаются, — соответственно, можно просто произвольным образом распределить в них всю исходную компанию.
Затем они переходят от одного такого набора к другому, постепенно добавляя людей в группы A или B за счет уменьшения X и Y. И авторы показывают, что одно из множеств A и B — в которых, напомним, люди соответственно попарно знакомы и незнакомы — достигает размера n до того, как исчерпается резерв из множеств X и Y.
Меняются эти множества в соответствии с одним из трех приемов:
1. Красный шаг. Если в X есть человек x, у которого много знакомых как в X, так и в Y, то можно его добавить в A, а в X и в Y оставить только его знакомых. Этот шаг применяется, если он не слишком сильно уменьшает размеры множеств X и Y и долю знакомых пар p между людьми из X и Y.
2. Большой синий шаг. Если не получается применить красный шаг, не сильно уменьшая X , то в X есть много людей, каждый из которых не знаком с очень многими из X. Тогда внутри X можно найти большую книгу незнакомств (S,T). Соответственно, можно добавить S к B (потому что люди в S не знакомы друг с другом) и заменить X на T.
3. Повышение плотности знакомств. Другая проблема, которая может помешать применению красного шага, — если в его результате слишком сильно снижается доля знакомых между X и Y (из-за чего потом при следующем применении первого шага будет слишком сильно уменьшаться множество Y). С этим можно бороться следующим образом: выбирается человек x из X, он добавляется к B, после чего в X остаются не знакомые с ним, а в Y — его знакомые. Оказывается, что при правильном выборе x размеры групп X и Y не сильно уменьшатся, а доля знакомств между X и Y увеличится.
Авторы комбинируют эти шаги и контролируют скорость, с которой уменьшаются размеры X и Y. Если исходный размер компании (и тем самым размеры X и Y) достаточно большие, группа A или B успеет вырасти до размера n — то есть в ней найдется n знакомых (или незнакомых) людей. И техника авторов позволяет это сделать для исходного размера компании в 3,9999n человек, вместо оценки экспоненциального порядка 4n, которая была известна раньше — решая, таким образом, вековую проблему.