x, y, z

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

Михаил Раскин

Комментарии: 0
Часть 1

Часть 2

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

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

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

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

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

Летняя школа «Современная математика», г. Дубна
28-29 июля 2017 г.
Комментарии: 0