Асимптотические задачи комбинаторики

Как выглядит большой случайный объект? Это не один вопрос, а целый класс очень интересных вопросов и замечательных тем. Зачастую ответ можно получить наглядным образом: просто поставив соответствующий эксперимент. Для части перечисленных ниже вопросов слушатели могут сделать это и сами — и это замечательное упражнение.

А вот доказать такой ответ иногда оказывается чрезвычайно сложно. На лекции мы обсудим и научимся давать ответы (пусть и не всегда доказательные) на некоторые такие вопросы:

  • Как выглядит случайный граф на N вершинах, будет ли он связен?
  • Как выглядит случайная перестановка N элементов, сколько и каких в ней независимых циклов?
  • Как выглядит случайное разбиение в сумму слагаемых достаточно большого числа N?
  • Если ацтекский бриллиант (см. рис. ниже) случайным образом разрезать на домино, как будет выглядеть такое разрезание?
  • Что будет, если случайным образом сложить N кубиков в углу комнаты, и как этот вопрос связан с предыдущими двумя?
Тематически этот рассказ примыкает к докладам Андрея Райгородского о случайных графах и Евгения Смирнова о разбиениях и диаграмме Юнга. Впрочем, его можно смотреть и независимо от них.