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

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

В понедельник 15.11 лекции не будет.
22.11 будет ДВЕ лекции, т.е. 17:40 - 19:10 и 19:20 - 20:50. Обе лекции будут в ауд.310.

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

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

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