Вероятностный метод

Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.

Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.

К распространённым инструментам, используемым в вероятностном методе, относятся неравенство Маркова, неравенство Чернова и локальная лемма Ловаса.

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

Следующие два примера применения вероятностного метода обсуждаются в деталях в книге «Доказательства из Книги» Мартина Айгнера и Гюнтера Циглера.

Нам нужно доказать существование раскраски в два цвета (скажем, красный и синий) рёбер полного графа с ${\displaystyle n}$ вершинами (при не очень больших значениях ${\displaystyle n}$) такой, что не существует полного  монохроматического подграфа с ${\displaystyle r}$ вершинами (то есть, с каждым ребром одного цвета).

Выберем цвета случайным образом. Цвет каждого ребра выбираем независимо с равной вероятностью красный или синий. Рассчитаем ожидаемое число полных монохроматических подграфов с ${\displaystyle r}$ вершинами следующим образом:

Для любого набора ${\displaystyle S}$ из ${\displaystyle r}$ вершин нашего графа, определим значение ${\displaystyle X(S)}$ равное 1, если каждое ребро с концами в ${\displaystyle S}$ одного цвета, и 0 в противном случае. Обратите внимание, что число монохроматических ${\displaystyle r}$-подграфов это сумма ${\displaystyle X(S)}$ по всем ${\displaystyle S}$.

Для любого ${\displaystyle S}$, математическое ожидание ${\displaystyle \mu }$ от ${\displaystyle X(S)}$ это вероятность того, что все ${\displaystyle {r \choose 2}}$ ребра в ${\displaystyle S}$ имеют тот же цвет. И значит

${\displaystyle \mu =2\cdot 2^{-{r \choose 2}}.}$

Множитель 2 появляется, потому что есть два возможных цвета.

То же самое справедливо для любого из ${\displaystyle {n \choose r}}$  возможных подмножеств с ${\displaystyle r}$ вершинами. Так, что математическое ожидание суммы ${\displaystyle X(S)}$ по всем ${\displaystyle S}$ равно

${\displaystyle M={n \choose r}\cdot \mu ={n \choose r}\cdot 2\cdot 2^{-{r \choose 2}}}$

Сумма математических ожиданий равна ожиданию суммы (независимо от того, являются ли переменные независимыми). Иначе говоря ${\displaystyle M}$ есть среднее число монохроматических ${\displaystyle r}$-подграфов случайно покрашенном графе.

Число монохроматических ${\displaystyle r}$-подграфов в случайной раскраске всегда будет целое число. Поэтому если ${\displaystyle M<1}$, то по крайней мере в одной раскраске, не должно быть полных монохроматических ${\displaystyle r}$-подграфов.

То есть, если

${\displaystyle 2\cdot {n \choose r}<2^{r \choose 2},}$

то

${\displaystyle R(r,r)>n}$

где ${\displaystyle R(r,r)}$ обозначает число Рамсея для ${\displaystyle r}$. В частности,  ${\displaystyle R(r,r)}$ растёт по крайней мере экспоненциально по ${\displaystyle r}$.

• Приведённое доказательство дано Эрдёшем.^[1]
• Этот метод не дает явный пример такой раскраски. Вопрос описания конкретного примера был открыт в течение более чем 50 лет.

Пусть даны целые положительные числа ${\displaystyle g}$ и ${\displaystyle k}$. Нам надо построить граф ${\displaystyle G}$ со всеми циклами циклы длины не менее ${\displaystyle g}$, и при этом хроматическое число G как минимум на ${\displaystyle k}$.

Зафиксируем большое целое число ${\displaystyle n}$. Рассмотрим случайный граф ${\displaystyle G}$ с ${\displaystyle n}$ вершинами, где каждое ребро в ${\displaystyle G}$ существует с вероятностью p = n^1/g−1. Покажем, что следующие два свойства выполняются с положительной вероятностью

Свойство 1. ${\displaystyle G}$ содержит не более чем ${\displaystyle n/2}$ циклов длины меньше, чем ${\displaystyle g}$. Точнее, вероятность того, что граф ${\displaystyle G}$ имеет не больше чем ${\displaystyle n/2}$ циклов длины меньше, чем ${\displaystyle g}$ стремится к 1 при ${\displaystyle n\to \infty }$.

Доказательство. Пусть ${\displaystyle X}$ — число циклов длины меньше, чем ${\displaystyle g}$. Число циклов длины ${\displaystyle i}$ в полном графе на ${\displaystyle n}$ с вершинами равно

${\displaystyle {\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}}$

и каждый из них содержится в ${\displaystyle G}$ с вероятностью pⁱ. Следовательно, по неравенству Маркова имеем

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}\cdot E[X]\leq {\frac {1}{n}}\cdot \sum _{i=3}^{g-1}p^{i}\cdot n^{i}={\frac {1}{n}}\cdot \sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}\cdot n^{\frac {g-1}{g}}=g\cdot n^{-{\frac {1}{g}}}=o(1).}$ ■

Свойство 2. ${\displaystyle G}$ не содержит независимое множество размера ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$. Точнее, вероятность того, что граф ${\displaystyle G}$ имеет независимое множество размера ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$ стремится к 1 при ${\displaystyle n\to \infty }$.

Доказательство. Пусть ${\displaystyle Y}$ обозначает размер наибольшего независимого множества в ${\displaystyle G}$. Очевидно, мы имеем

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

когда

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil .}$ ■

Поскольку ${\displaystyle G}$ имеет эти два свойства, мы можем извлечь максимум ${\displaystyle n/2}$ вершин из ${\displaystyle G}$, чтобы получить новый граф ${\displaystyle G'}$ с ${\displaystyle n'\geq n/2}$ вершинами, содержащий только циклы длины не более ${\displaystyle g}$. Мы видим, что ${\displaystyle G'}$ имеет независимый набор размера ${\displaystyle \lceil {\frac {n'}{k}}\rceil }$. ${\displaystyle G'}$ может только быть разделён по крайней мере на ${\displaystyle k}$ независимых множеств, и, следовательно, имеет хроматическое число, по крайней мере ${\displaystyle k}$.

• Этот результат объясняет, почему вычисление хроматического числа графа является сложной задачей. Даже при отсутствии локальных причин (таких как малые циклы) хроматическое число может быть произвольно большим.

• Случайный граф

• Айгнер М. Циглер Г. Доказательства из Книги. Лучшие доказательства со времен Евклида до наших дней. — Издательство «Лаборатория знаний» (ранее «БИНОМ. Лаборатория знаний»), 2014. — ISBN 978-5-9963-2736-2.

• Алон Н., Спенсер Дж. Вероятностный метод, Бином, 2007, с. 320, 1100 экз. ISBN 978-5-94774-556-6

• А. М. Райгородский. Графы с большим хроматическим числом и большим обхватом (рус.) // Матем. просв., сер. 3. — 2016. — Т. 20. — С. 228—237.

На английском

• Erdős, P. Graph theory and probability (неопр.) // Canad. J. Math.. — 1959. — Т. 11, № 0. — С. 34—38. — doi:10.4153/CJM-1959-003-9. Архивировано 18 июля 2011 года.

• J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.

• Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics

1. ↑ Erdös, P. Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53, (1947). 292–294.