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

Дальше увидим первый пример применения очень мощного результата в контексте вероятностного метода: локальная лемма Ловаса позволяет нам доказать, что конкретное множество нежелательных событий можно избежать, если каждое из них достаточно невероятно и каждое из них зависит от немногих других событий. Мы с помощью локальной леммы Ловаса покажем, что маленькие формулы в конъюнктивной нормальной форме всегда выполнимы.