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

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

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

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

ИсторияПравить

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

ПримерыПравить

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

Нижняя оценка на число РамсеяПравить

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

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

Для любого набора   из   вершин нашего графа, определим значение   равное 1, если каждое ребро с концами в   одного цвета, и 0 в противном случае. Обратите внимание, что число монохроматических  -подграфов это сумма   по всем  .

Для любого  , математическое ожидание   от   это вероятность того, что все   ребра в   имеют тот же цвет. И значит

 

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

То же самое справедливо для любого из    возможных подмножеств с   вершинами. Так, что математическое ожидание суммы   по всем   равно

 

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

Число монохроматических  -подграфов в случайной раскраске всегда будет целое число. Поэтому если  , то по крайней мере в одной раскраске, не должно быть полных монохроматических  -подграфов.

То есть, если

 

то

 

где   обозначает число Рамсея для  . В частности,    растёт по крайней мере экспоненциально по  .

ЗамечанияПравить

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

Построение графа без коротких циклов с большим хроматическим числомПравить

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

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

Свойство 1.   содержит не более чем   циклов длины меньше, чем  . Точнее, вероятность того, что граф   имеет не больше чем   циклов длины меньше, чем   стремится к 1 при  .

Доказательство. Пусть   — число циклов длины меньше, чем  . Число циклов длины   в полном графе на   с вершинами равно

 

и каждый из них содержится в   с вероятностью pi. Следовательно, по неравенству Маркова имеем

 

Свойство 2.   не содержит независимое множество размера  . Точнее, вероятность того, что граф   имеет независимое множество размера   стремится к 1 при  .

Доказательство. Пусть   обозначает размер наибольшего независимого множества в  . Очевидно, мы имеем

 

когда

 

Поскольку   имеет эти два свойства, мы можем извлечь максимум   вершин из  , чтобы получить новый граф   с   вершинами, содержащий только циклы длины не более  . Мы видим, что   имеет независимый набор размера  .   может только быть разделён по крайней мере на   независимых множеств, и, следовательно, имеет хроматическое число, по крайней мере  .

ЗамечанияПравить

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

См. такжеПравить

ЛитератураПравить

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

FootnotesПравить

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