City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Генерируй и меняй, локальная лемма Ловаса
Randomized Algorithms

What: Lecture
When: Wednesday, 24 March 2021, 14:10–15:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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

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