Что: | Лекция |
Когда: | Среда, 24 марта 2021, 18:10–19:45 |
Где: | НГУ, ауд. 5210, НГУ, новый корпус |
В этой лекции сначала увидим ещё больше примеров применения вероятностного подхода. Применяя аргументы, основывающиеся на математическом ожидании, докажем нижнюю оценку на число пересечений рёбер в рисунке графа на плоскости. С помощью подхода генерируй и меняй
докажем нижнюю оценку на мощность наибольшего независимого множества в графе.
Дальше увидим первый пример применения очень мощного результата в контексте вероятностного метода: локальная лемма Ловаса позволяет нам доказать, что конкретное множество нежелательных событий можно избежать, если каждое из них достаточно невероятно и каждое из них зависит от немногих других событий. Мы с помощью локальной леммы Ловаса покажем, что маленькие формулы в конъюнктивной нормальной форме всегда выполнимы.