Дискретные структуры: архив курса

Интерактивная карта курса

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

Осенний семестр: базовые понятия

Основы комбинаторики

• Основные правила комбинаторики: правило сложения, правило умножения, принцип Дирихле, формула включений и исключений. [ВВВ, §§4,13,131] [Ша, гл. 1]
• Размещения, перестановки и сочетания. Бином Ньютона, полиномиальная формула. Некоторые тождества с биномиальными коэффициентами. [ВВВ, §§5,19,20,23,24,33] [Ша, гл. 1]
• Оценки для факториалов и биномиальных коэффициентов. Формула Стирлинга (б/д). Запись \((c+o(1))^n\). Оценки биномиальных коэффициентов вида . Асимптотика для \(\binom{n}{k}\) при \(k=o(\sqrt{n})\). Оценки для \(\binom{n}{k}\) при бо́льших \(k\). [ГКП, §4.4 и гл. 9] [КЛРШ, гл. 3]
• Функция Мёбиуса. Формула обращения Мёбиуса. Применение формулы обращения Мёбиуса для подсчёта числа циклических последовательностей. [Са, гл. 2 §3]
• Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные формулы. Число упорядоченных разбиений. Диаграммы Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений. Формула Харди—Рамануджана (б/д). [ВВВ, гл. 4]
• Линейные рекуррентные соотношения с постоянными коэффициентами. Соотношения 2-го порядка — с доказательством, соотношения большего порядка — только формулировка. Числа Фибоначчи. [ВВВ, §§94, 101—104]
• Степенные ряды и производящие функции. Пример тождества, доказываемого с помощью степенных рядов. Теоремы о сходимости степенных рядов (б/д). Числа Каталана. Нахождение сумм с участием биномиальных коэффициентов, чисел Фибоначчи и т.д. [ВВВ, гл. 8] [ГКП, гл. 7]

Конечные алгебраические структуры

• Алгебраические структуры: группы, поля. Аксиоматика. Примеры конечных и бесконечных групп и полей. [Любой учебник общей алгебры] [КМ, §1] [ББ, §7.3, 7.5, 10.1]
• Теорема Кэли об универсальности групп подстановок. Понятия действия группы на множестве и орбиты элемента. Примеры. [КМ, §11, 12]
• Разложение группы по подгруппе. Теорема Лагранжа. Теорема Силова о существовании подгруппы заданной мощности. [КМ, §§2, 11.1] [ББ, §§7.9—7.11]
• Лемма Бёрнсайда. Перечислительная теорема Редфилда—Пойи. [ВВВ, гл. 9]
• Неприводимые многочлены: их свойства и количество. Построение конечных полей.

Основные понятия теории графов и гиперграфов

• Определение графа, орграфа, мультиграфа, псевдографа и т.д. Изоморфизм графов. Число независимости, кликовое число. [ЕМСТ, §§1,2,4,25,26,53]
• Маршруты в графах. Гамильтоновы и эйлеровы циклы. Достаточное условие Оре существования гамильтонова цикла. Критерий существования эйлерова цикла. Алгоритм Флёри. Построение последовательностей Де Брёйна на основе эйлеровых циклов. [ЕМСТ, §§43,44] [РаЭ, гл. 9]
• Раскраски графов. Простейшие оценки хроматического числа и хроматического индекса. Теорема Кёнига о хроматическом индексе двудольных графов. Хроматический многочлен.
• Планарные графы. Миноры. Критерий Вагнера. Теорема о пяти красках.
• Паросочетания в двудольных графах. Теорема Холла. Системы различных представителей, перманенты.
• Понятие гиперграфа. Аналоги графовых терминов для гиперграфов. Трансверсальные множества (системы общих представителей). Жадный алгоритм. Оценки мощности жадного покрытия.

Весенний семестр: продвинутые теоремы, вероятностные и алгебраические методы

• Теорема Алона о нулях многочленов и некоторые её комбинаторные следствия: теорема Коши—Давенпорта, теорема о покрытии вершин куба плоскостями, теорема о существовании регулярных подграфов в почти регулярных графах. [Al]
• Теорема Турана о графе с заданным кликовым числом и максимальным количеством рёбер. Аналог задачи Турана для двудольных графов: проблема Заранкевича. Решение проблемы Заранкевича в частном случае для графов без K2,2. Вероятностная нижняя оценка чисел Заранкевича.
• Теория Рамсея. Числа Рамсея \(R(s,t)\): точные значения для \(s=1,2\); верхняя оценка Эрдёша—Секереша, её следствие для диагональных чисел Рамсея; нижняя оценка диагональных чисел с помощью простого вероятностного метода. Теорема Рамсея для гиперграфов (б/д). [АС, §3.1]
• Линейно-алгебраический метод: теорема Франкла—Уилсона, конструктивная нижняя оценка чисел Рамсея. [РаЛ, гл. 5] [РаЭ, гл. 5]
• Локальная лемма Ловаса: симметричный и общий случаи. Уточнение нижней оценки диагональных чисел Рамсея с её помощью. Идея нижней оценки чисел \(R(s,3)\) [АС, §§5.1,5.3]
• Некоторые применения вероятностного метода в теории графов. Теорема Эрдёша о существовании графов с произвольно большим обхватом и хроматическим числом. Оценка числа независимости. Оценка числа скрещиваний.
• Частично-упорядоченные множества. Булеан. Теоремы Лубелла—Ямамото—Мешалкина и Шпернера о размере антицепи в булеане. Разложение ЧУМ на цепи и антицепи. Вывод теоремы Холла из теоремы Дилуорта.
• \(t\)-пересекающиеся гиперграфы. Теорема Эрдёша—Ко—Радо. Теорема Альсведе—Хачатряна (без доказательства). Теорема Фишера. [РаЭ, §10.1]
• Проекции семейств на множества. Размерность Вапника—Червоненкиса. Верхняя оценка мощности семейств с ограниченной VC-размерностью. Верхняя оценка VC-размерности измельчений. Теорема Хаусслера—Вельцля об \(\epsilon\)-сетях для семейств с ограниченной VC-размерностью (без доказательства) и её геометрическое следствие. [РаС, гл. 6]

Литература по курсу

• [АС] Н. Алон, Дж. Спенсер. Вероятностный метод. — М.: Бином, 2007.
• [АЦ] М. Айгнер, Г. Циглер. Доказательства из Книги. — М.:Мир, 2006.
• [ББ] Г. Биркгоф, Т. Барти. Современная прикладная алгебра. — М.: Мир, 1976.
• [ВВВ] Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин. Комбинаторика. — М: ФИМА, МЦНМО, 2010.
• [ГС] Г. П. Гаврилов, А. А. Сапоженко. Задачи и упражнения по дискретной математике. — М.: Физматлит, 2006.
• [ГКП] Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Основание информатики. — М.: Бином. Лаборатория знаний, Мир, 2009.
• [ЕМСТ] В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Книжный дом «Либроком», 2009.
• [КМ] М. И. Каргаполов, Ю. И. Мерзляков. Основы теории групп. 3-е изд. — М.: Наука, 1982.
• [КЛРШ] Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
• [РаВ] А. М. Райгородский. Вероятность и алгебра в комбинаторике. — М.: МЦНМО, 2008.
• [РаЛ] А. М. Райгородский. Линейно-алгебраический метод в комбинаторике. — М.: МЦНМО, 2007.
• [РаЭ] А. М. Райгородский. Экстремальные задачи теории графов и анализ данных. — М.-Ижевск: Институт компьютерных исследований, 2008.
• [РаС] А. М. Райгородский. Системы общих представителей в комбинаторике и их приложения в геометрии. — М.: МЦНМО, 2009.
• [Са] В. Н. Сачков. Введение в комбинаторные методы дискретной математики. — М.: МЦНМО, 2004.
• [Ха] Ф. Харари. Теория графов. — М.: Мир, 1973.
• [Ша] А. Х. Шахмейстер. Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
• [Al] N. Alon. Combinatorial Nullstellensatz // Combinatorics, Probability and Computing. 8 (1999), pp. 7-29.
• [Ju] S. Jukna. Extremal Combinatorics (With Applications in Computer Science). — Springer, 2001.