Эрдёш: вероятность как инструмент существования

Вопрос

Теорема Рамсея говорит: как ни раскрашивай рёбра достаточно большого полного графа в два цвета, одноцветная клика на $k$ вершинах появится. Наименьшее число вершин, при котором это уже неизбежно, обозначают $R(k,k)$.

Верхняя оценка $R(k,k)\leqslant 4^{k}$ была известна с 1935 года. А вот снизу — то есть насколько долго удаётся избегать одноцветной клики — не было почти ничего: чтобы дать нижнюю оценку, надо предъявить хорошую раскраску, а придумать её никто не умел.

Три строки

Пал Эрдёш в 1947 году в статье «Some remarks on the theory of graphs» (три страницы в Bulletin AMS) поступил так.

Возьмём полный граф на $n$ вершинах и покрасим каждое ребро независимо, подбрасывая монету: красное или синее с вероятностью $\tfrac12$.

Фиксируем какие-нибудь $k$ вершин. У них $C_{k}^{2}=\dfrac{k(k-1)}{2}$ рёбер, и вероятность, что все они одного цвета, равна

$$2\cdot 2^{-k(k-1)/2} = 2^{\,1-k(k-1)/2}.$$

Наборов из $k$ вершин ровно $C_{n}^{k}$. Значит, среднее число одноцветных клик не превосходит

$$C_{n}^{k}\cdot 2^{\,1-k(k-1)/2}.$$

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

Осталось посчитать. Положим $n = 2^{k/2}$ и воспользуемся $C_{n}^{k}\leqslant n^{k}/k!$:

$$\frac{n^{k}}{k!}\cdot 2^{\,1-k(k-1)/2} = \frac{2^{k^{2}/2}}{k!}\cdot 2^{\,1-k^{2}/2+k/2} = \frac{2^{\,1+k/2}}{k!} < 1 \quad\text{при } k\geqslant 3 .$$

(Проверка для $k=3$: $2^{2{,}5}/6 = 5{,}66/6 < 1$.) Следовательно,

$$R(k,k) > 2^{\,k/2}.$$

$\blacksquare$

Что здесь странно

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

И при этом мы не можем предъявить ни одной.

Это не временное неудобство. Задача явного построения графов РамсеяФрэнк Пламптон Рамсейанглийский математик, философ и экономист · 1903–1930Доказал, что полный беспорядок невозможен: в любой достаточно большой структуре найдётся большой упорядоченный кусок. Теорема была у него вспомогательной леммой. Умер в двадцать шесть лет, успев основать три… открыта и сегодня: явные конструкции долго давали клики размера порядка $\sqrt{\log n}$ вместо $\log n$, и только с 2015 года (Чаттопадхьяй и Цукерман) удалось подойти к нужному порядку с точностью до $(\log\log n)^{c}$. Разрыв между «почти всё сено — иголки» и «вот иголка» оказался одной из самых упорных трудностей в дискретной математике.

Границы $2^{k/2} < R(k,k) \leqslant 4^{k}$ Эрдёш поставил в 1947-м, и до 2023 года никто не сдвинул ни одну из них экспоненциально.

Метод, а не приём

Эрдёш не был первым, кто применил такое рассуждение: Тибор Селе в 1943 году так же доказал существование турниров с большим числом гамильтоновых путей. Но 1947 год — момент, когда приём стал методом: Эрдёш применял его снова и снова тридцать лет, и в 1974 году вышла книга Эрдёша и Спенсера, а затем — «The Probabilistic Method» Алона и Спенсера, учебник, по которому этот способ рассуждения учат до сих пор.

Метод довольно быстро оброс техникой:

• первый момент — то, что мы только что видели: если среднее числа плохих объектов меньше единицы, хороший объект есть;
• удаление — если среднее не меньше единицы, возьмём случайный объект и удалим из него все плохие места; оценим, сколько останется;
• второй момент — если дисперсия мала, случайная величина близка к среднему почти всегда;
• локальная лемма Ловаса (1975, Эрдёш и Ловас) — если плохих событий много, но каждое зависит лишь от немногих других, вероятность избежать всех сразу положительна, пусть и чудовищно мала.

Общий смысл всех четырёх: случайность оказалась способом строить, а не только способом описывать неопределённость. В соседней линии тот же поворот происходит в те же годы — Улам и фон Нейман в 1946-м начинают вычислять детерминированные величины подбрасыванием монеты.

Человек

О Пале Эрдёше (1913–1996) написано больше анекдотов, чем о любом другом математике XX века, и почти все они правдивы.

Около 1500 статей — больше, чем у кого бы то ни было, кроме ЭйлераЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя., — и более 500 соавторов. Отсюда «число Эрдёша»: расстояние от вас до него в графе соавторства. У ЭйнштейнаАльберт Эйнштейннемецкий физик-теоретик · 1879–1955Единственный физик в этом справочнике по праву математика: чтобы записать тяготение, ему понадобилась геометрия Римана — и он потратил на её освоение семь лет. оно равно двум.

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

Свой язык: дети — «эпсилоны», женщины — «боссы», мужчины — «рабы», Бог — «Верховный Фашист», который прячет от людей Книгу с самыми красивыми доказательствами. За решённые задачи он платил из своего кармана — от 25 до 10 000 долларов, в зависимости от трудности; часть этих премий не выплачена до сих пор, потому что задачи не решены.

Один эпизод стоит рядом с этой линией отдельно: в 1948 году Эрдёш и Атле СельбергАтле Сельбергнорвежский и американский математик · 1917–2007В оккупированной Норвегии в одиночку доказал, что положительная доля нулей дзета-функции лежит на критической прямой; потом получил элементарное доказательство теоремы о простых числах — и рассорился из-за… нашли элементарное доказательство теоремы о распределении простых чисел, и это кончилось тяжёлой ссорой о приоритете.

Он умер в 1996 году в Варшаве, на конференции, восьмидесяти трёх лет, — примерно так, как и хотел.

Что из этого выросло

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

А прямо сейчас, в следующей точке линии, тот же приём применит человек, ничего не знавший про Будапешт: доказывая существование хороших помехоустойчивых кодов, Шеннон возьмёт случайный код и покажет, что он почти наверняка годится. Ни одного явного кода в его статье нет.

Задача. Посчитайте среднее число одноцветных четвёрок при случайной раскраске рёбер $K_6$ и $K_7$. Какая нижняя оценка для $R(4,4)$ отсюда следует и насколько она далека от истины?
(Ответ: вероятность одноцветности четвёрки равна $2^{1-6}=1/32$. Для $n=6$: $C_6^4=15$, среднее $15/32\approx0{,}47<1$ — значит, $R(4,4)>6$. Для $n=7$: $C_7^4=35$, среднее $35/32\approx1{,}09>1$ — рассуждение не проходит. Истинное значение $R(4,4)=18$. Метод даёт правильный порядок роста, но на малых числах очень груб.)

Следующая точка: Мюррей-Хилл — где тем же рассуждением докажут, что хорошие коды существуют, и заодно определят, что такое информация.