Бери ниже

В комбинаторике прямо сейчас происходит много весьма интересных событий, это одна из самых бурно развивающихся областей математики. Но среди них отдельно выделяется новая работа Марсело Кампоса, Саймона Гриффитса, Роберта Морриса (Рио-де-Жанейро) и Джулиана Сахасрабуде (Кембридж), посвященная оценке чисел Рамсея. В чем с этими числами проблема и как ее недавно решили, рассказывает математик Фёдор Петров, профессор СПбГУ и ведущий научный сотрудник ПОМИ РАН.

Числа Рамсея

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

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

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

А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это доказал английский математик Фрэнк Пламптон Рамсей в 1930 году. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n,k) и  называется числом Рамсея. Выше мы установили, что R(3,3) = 6. 

Считать числа Рамсея очень трудно. Известно, что:

• R(4,3) = 9,
• R(4,4) = 18,
• R(3,5) = 14,
• R(4,5) = 25 (это сложно).

А вот 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) < 2^n + k (достаточно заметить, что 2^{n + (k − 1)} + 2^{(n − 1) + k} = 2 × 2^{n + k − 1} = 2^n + k, и применить индукцию).

Если сосредоточиться на диагональных числах Рамсея, то есть на случае n = k, получаем R(n,n) < 4ⁿ. 

С другой стороны, существует оценка снизу: R(n,n) > 2^n/2. Она получается с помощью вероятностного метода Эрдёша. А именно, допустим, что для каждой пары людей то, знакомы они или нет, определяется подкидыванием монетки — то есть они оказываются знакомы с вероятностью ½, причем для каждой пары монетка подкидывается отдельно. Тогда вероятность, что в группе размером не больше 2^n/2 не найдутся ни n знакомых, ни n незнакомых пар, положительна — а значит, хотя бы один пример такой конфигурации знакомств существует.

Поэтому величина R(n,n) заключена между двумя экспонентами: 

(√2)ⁿ < R(n,n) < 4ⁿ.

А можно ли улучшить одну из этих констант — √2 или 4 — так, чтобы неравенство по-прежнему было верно при всех достаточно больших n? На протяжении десятилетий эта задача считалась одной из самых важных в комбинаторике. Не столько из-за важности чисел Рамсея самих по себе (хотя и у них много приложений), сколько как вопрос, проверяющий меру нашего понимания больших комбинаторных структур, — подобно тому как Великая теорема Ферма долгое время проверяла наше понимание арифметики.

С нижней оценкой уже давно нет никаких сколько-то серьезных продвижений, а по верхней около 15 лет назад появилась работа Дэвида Конлона, который смог поделить 4ⁿ на функцию, растущую быстрее любого многочлена, но медленнее экспоненты. 

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

В чем суть

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

Предыдущие улучшения верхних оценок чисел Рамсея — в работах Томассена, а затем Конлона и Саха — основывались на идее так называемой . Подход в новой работе совершенно другой. Но в ней используется понятие книги, которое ввели их предшественники. 

Книга знакомств — это пара непересекающихся множеств S иT в нашей компании, в которой люди из S знакомы и друг с другом, и со всеми из T. Аналогично определяется и книга незнакомств.

Авторы берут любую компанию, в которой есть хотя бы 3,9999ⁿ людей, и начинают искать в ней n знакомых (или незнакомых) людей. Для этого они последовательно выделяют в ней подмножества A, B, X, Y, удовлетворяющие некоторым условиям, обобщающим понятие книги:

• в A все попарно знакомы как друг с другом, так и со всеми в X и Y, 
• в B все попарно незнакомы, а также незнакомы с людьми из X.

При этом авторы также отслеживают величину 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,9999ⁿ человек, вместо оценки экспоненциального порядка 4ⁿ, которая была известна раньше — решая, таким образом, вековую проблему.