Аннотация:
Иногда мы хотим доказать, что какой-нибудь объект существует. Разумеется, можно медленно и методично объект построить. Но это что-то делать надо, а хочется получить кое-что задаром. Поэтому мы просто возьмём случайный объект и заметим, что он подходит с ненулевой вероятностью. Это позволяет избежать занудной конструкции. Заодно можно спрятать в доказательстве незаметную ошибку.
Для понимания курса нужно будет знать определение независимых событий. Понимать, что это такое, не обязательно, всё равно в ходе курса такое понимание (или только его иллюзию?) можно будет утратить.
Примерная программа курса
Построим что-нибудь. Нижняя оценка на число Рамсея. Раскраски таблиц с одноцветными прямоугольниками и без.
Ожидания и реальность: вероятность больших отклонений, разные оценки и их применимость.
Графы-экспандеры.
Мошенничество и никакой ловкости рук: почему важно следить за независимостью.
Буквоедские изыскания: почему «несжимаемый» файл очень легко породить случайно и доказуемо совершенно невозможно совсем неслучайно.
Применение жути в мирных целях: формулировка и применение леммы Ловаша о локальной зависимости.
Обратная связь: