Вероятностный метод
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике (например, метод вероятностного округления) и теории информации.
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
К распространённым инструментам, используемым в вероятностном методе, относятся неравенство Маркова, неравенство Чернова и локальная лемма Ловаса.
Наиболее известные применения этого метода связано с Эрдёшем. Тем не менее, вероятностный метод применялся и до работ Эрдёша в этом направлении. Например, Селеш в 1943 использовал метод при доказательстве того, что существуют турниры, содержащие большое количество Гамильтоновых циклов.
Следующие два примера применения вероятностного метода обсуждаются в деталях в книге «Доказательства из Книги» Мартина Айгнера и Гюнтера Циглера.
Нам нужно доказать существование раскраски в два цвета (скажем, красный и синий) рёбер полного графа с вершинами (при не очень больших значениях ) такой, что не существует полного монохроматического подграфа с вершинами (то есть, с каждым ребром одного цвета).
