Рамсей: полный беспорядок невозможен

Утверждение

Начнём с версии, которую можно рассказать за минуту и проверить на салфетке.

Задача о вечеринке. В комнате шесть человек. Докажите, что среди них найдутся либо трое попарно знакомых, либо трое попарно незнакомых.

Решение. Возьмём человека $A$. Остальных пятеро, и с каждым он либо знаком, либо нет. По принципу ящиков хотя бы в одной из двух групп — знакомых или незнакомых — окажется не меньше трёх человек. Пусть это трое знакомых $A$: $B$, $C$, $D$.

Если какие-то двое из них знакомы между собой — скажем, $B$ и $C$, — то $A$, $B$, $C$ попарно знакомы, и готово. Если же никакие двое из $B,C,D$ не знакомы, то они трое попарно незнакомы, и тоже готово. $\blacksquare$

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

На языке графов: раскрасим рёбра полного графа $K_6$ в два цвета; обязательно найдётся одноцветный треугольник. Число 6 обозначают $R(3,3)=6$.

Теорема

Фрэнк Пламптон Рамсей (1903–1930) доказал общее утверждение в статье «On a problem of formal logic» (1930). Заметим контекст: работа посвящена разрешимости одного класса формул логики первого порядка, и теорема о раскрасках была там вспомогательной леммой. Автор не считал её главным результатом.

Теорема Рамсея. Для любых $r$ и $k$ существует такое $N$, что при любой раскраске рёбер полного графа на $N$ вершинах в $k$ цветов найдётся одноцветный полный подграф на $r$ вершинах.

Наименьшее такое $N$ называется числом Рамсея $R(r_1,\dots,r_k)$.

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

Числа, которых никто не знает

А вот дальше начинается то, из-за чего теория Рамсея знаменита.

	$R(3,3)$	$R(4,4)$	$R(5,5)$	$R(6,6)$
Значение	6	18	$43\ \dots\ 46$	$102\ \dots\ 160$

Известны ровно два нетривиальных значения. $R(5,5)$ не вычислено, хотя задача формулируется на школьном уровне и перебор конечен: надо проверить раскраски полного графа на 43–46 вершинах. Их порядка $2^{C_{45}^{2}}=2^{990}$ — больше, чем атомов в наблюдаемой Вселенной в степени десять.

ЭрдёшуПал Эрдёшвенгерский математик · 1913–1996Полторы тысячи статей, пятьсот соавторов, ни дома, ни семьи, ни постоянной работы — сорок лет он ездил из университета в университет с одним чемоданом. принадлежит фраза, которую стоит привести целиком:

Представьте, что инопланетяне высадились на Земле и потребовали сообщить им $R(5,5)$, иначе уничтожат планету. Тогда следовало бы бросить все ресурсы человечества на вычисление. Но если бы они спросили $R(6,6)$, лучше было бы попытаться уничтожить их.

Оценки. Верхняя граница $R(k,k)\leqslant4^{k}$ известна с 1935 года (Эрдёш и Секереш) и почти не улучшалась. Нижняя — $R(k,k)>2^{k/2}$ — получена Эрдёшем в 1947 году вероятностным методом. Между $\sqrt2^{\,k}$ и $4^{k}$ лежит пропасть, и сузить её не удавалось семьдесят пять лет.

Сдвиг произошёл недавно: в 2023 году Кампос, Гриффитс, Моррис и Сахасрабудхе улучшили верхнюю оценку до $(4-\varepsilon)^{k}$ с явной константой — первое экспоненциальное продвижение с 1935 года. Новость обсуждалась далеко за пределами комбинаторики.

Счастливый конец

Теорему переоткрыли в Будапеште в 1933–35 годах, и обстоятельства этого стоят рассказа.

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

Секереш и Кляйн поженились. Эрдёш назвал результат «задачей о счастливом конце» (happy ending problem) — потому что она кончилась свадьбой. Секереши прожили вместе шестьдесят с лишним лет и умерли в 2005 году с разницей в час.

Сама задача, кстати, решена не полностью: гипотеза Эрдёша — Секереша о том, что для выпуклого $n$-угольника достаточно $2^{n-2}+1$ точек, доказана лишь асимптотически (Суком, 2016).

Числа, которые не помещаются

Теория Рамсея прославилась ещё и величиной участвующих в ней чисел.

Число Грэма возникло в 1971 году как верхняя оценка в одной задаче о раскраске рёбер многомерного куба. Оно определяется башней операций, каждая из которых чудовищно быстрее предыдущей, и настолько велико, что его нельзя записать никакой позиционной записью — во Вселенной не хватит места для цифр. Одно время оно значилось в Книге рекордов Гиннесса как наибольшее число, использованное в математическом доказательстве. Правильный ответ в той задаче, по нынешним оценкам, лежит между 13 и очень небольшим числом — то есть оценка Грэма была завышена невообразимо.

Автор

Рамсей прожил двадцать шесть лет и успел оставить след в трёх науках.

В философии — работы о вероятности как степени убеждённости (предшественник байесовского подхода в его субъективистской версии), о истине и о смысле; он был другом и оппонентом Витгенштейна, перевёл на английский «Логико-философский трактат» в девятнадцать лет.

В экономике — две статьи, каждая из которых основала направление: о оптимальном налогообложении (правило Рамсея) и об оптимальном сбережении (модель роста Рамсея), — обе востребованы до сих пор.

В математике — эта теорема.

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

Задача. Докажите, что $R(3,3)>5$, предъявив раскраску рёбер $K_5$ в два цвета без одноцветного треугольника.
(Ответ: расположите пять вершин по кругу; рёбра-стороны покрасьте в красный, рёбра-диагонали — в синий. И красные, и синие рёбра образуют по пятиугольнику-циклу длины 5, а в цикле длины 5 треугольников нет.)

Следующая точка: Будапешт — где разрозненные задачи о графах впервые соберут в дисциплину и напишут ей учебник.