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