А.М.Райгородский

Вероятностные методы в комбинаторике

Спецкурс посвящен одному из самых красивых и современных разделов комбинаторного анализа. Несмотря на то, что в конечном счете будет изложена весьма нетривиальная вероятностно-комбинаторная техника, спецкурс будет доступен первокурсникам.

Программа курса:

1. Основная идея вероятностного метода. Примеры: числа Рамсея, задачи комбинаторной теории чисел.
2. Линейность математического ожидания. Примеры: задачи теории графов, комбинаторной геометрии и пр.
3. Альтернирование. Еще о числах Рамсея. Раскраски графов и гиперграфов.
4. Метод второго момента. Случайные графы. Распределение числа делителей.
5. Локальная лемма Ловаса. Числа Рамсея. Снова о раскрасках гиперграфов. Покрытие графов линейными лесами.
6. Метод моментов. Пуассоновская аппроксимация. Применение к задачам о случайных графах.
7. Мартингалы. Неравенство Азумы. Хроматическое число случайного графа.