На главную страницу НМУ

В ближайшую среду (8 апреля) лекции не будет.
Следующая лекция состоится 15 апреля по расписанию.

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

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

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

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

1. Основная идея вероятностного метода. Примеры: числа Рамсея, задачи комбинаторной теории чисел.

2. Линейность математического ожидания. Примеры: задачи теории графов, комбинаторной геометрии и пр.

3. Альтернирование. Еще о числах Рамсея. Раскраски графов и гиперграфов.

4.Метод второго момента. Случайные графы. Распределение числа делителей.

5. Локальная лемма Ловаса. Числа Рамсея. Снова о раскрасках гиперграфов. Покрытие графов линейными лесами.

6. Метод моментов. Пуассоновская аппроксимация. Применение к задачам о случайных графах.

7. Мартингалы. Неравенство Азумы. Хроматическое число случайного графа.