Михаил Александрович Раскин

Случайно существующие объекты (вероятностные доказательства существования)

М. А. Раскин планирует провести 2 занятия.

Доступны 2 видеозаписи курса.

Иногда мы хотим доказать, что какой-нибудь объект существует. Разумеется, можно медленно и методично объект построить. Но это что-то делать надо, а хочется получить кое-что задаром. Поэтому мы просто возьмём случайный объект и заметим, что он подходит с ненулевой вероятностью. Это позволяет избежать занудной конструкции. Заодно можно спрятать в доказательстве незаметную ошибку.

Для понимания курса нужно будет знать определение независимых событий. Понимать, что это такое, не обязательно, всё равно в ходе курса такое понимание (или только его иллюзию?) можно будет утратить.

Примерная программа курса

1. Построим что-нибудь. Нижняя оценка на число Рамсея. Раскраски таблиц с одноцветными прямоугольниками и без.
2. Ожидания и реальность: вероятность больших отклонений, разные оценки и их применимость.
3. Графы-экспандеры.
4. Мошенничество и никакой ловкости рук: почему важно следить за независимостью.
5. Буквоедские изыскания: почему «несжимаемый» файл очень легко породить случайно и доказуемо совершенно невозможно совсем неслучайно.
6. Применение жути в мирных целях: формулировка и применение леммы Ловаша о локальной зависимости.

Organization Committee e-mail:
dubna@mccme.ru