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

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

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

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

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

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

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

Rambler's Top100