2010/2011 — Весенний семестр

Разделы

Экстремальные проблемы теории гиперграфов

Семестровый курс по выбору.

Кафедра анализа данных (ФИВТ).

Проходит: по четвергам с 18:40 до 20:00, первое занятие 17 февраля. Аудитория: 430 ГК.

Лектор: Шабанов Дмитрий Александрович, к. ф.-м. н.

От слушателей потребуется только знание основных понятий теории вероятностей. Приглашаются все желающие.

Одним из столпов современной экстремальной комбинаторики является экстремальная теория множеств, основы которой были заложены в 30-е годы XX века Ф. Рамсеем, П. Тураном, П. Эрдешем и др. В свою очередь, одной из наиболее простых и естественных комбинаторных структур является гиперграф. Гиперграфом в дискретной математике принято называть совокупность подмножеств конечного множества. Название «гиперграф» говорит о том, что данная конечная система множеств рассматривается как естественное обобщение понятия обычного графа. Для гиперграфа, как и для графа, можно определить понятия цикла, множества независимости, степени вершины, хроматического числа и т.д. В курсе пойдет речь об экстремальных комбинаторных задачах, в основном связанных с раскрасками гиперграфов. Подобные задачи, весьма простые по формулировке, зачастую совсем тривиально решаются для графов, но для гиперграфов в этих задачах не найдено даже асимптотических ответов.

Еще одним важным аспектом, который будет подробно обсуждаться в курсе, является исторически сложившаяся тесная связь экстремальных задач о раскрасках гиперграфов с вероятностными методами дискретной математики, активное развитие которых началось еще в 50-60-е годы прошлого века. В начале XXI века эти методы активно применяются в теоретической информатике, теории чисел и многих других разделах современной математики, что еще раз подчеркивает важность их изучения.

В курсе будут представлены как классические теоремы 60-70-х годов, так и исследования последних десяти лет.

Краткое содержание спецкурса:

Основные понятия теории гиперграфов. Теорема Турана.

Задача Эрдеша — Хайнала о раскрасках равномерных гиперграфов. Теоремы Эрдеша, Алона, Плухара, Радхакришнана и Сринивасана.
Локальная Лемма и достаточное условие раскрашиваемости гиперграфа.
Теорема Эрдеша и Ловаса о существовании равномерного гиперграфа со сколь угодно большими обхватом и хроматическим числом.
Гиперграфы — клики и задачи об их покрытии.
Предписанные раскраски, асимптотика предписанного хроматического числа полных многодольных графов.
Элементы теории Рамсея, оценки в теореме Рамсея и теореме Ван дер Вардена об арифметических прогрессиях.

Что развивает курс (данные для «Вектора»)

Алгоритмы и методы анализа данных (курс сфокусирован на этом)

Информация о развиваемых компетенциях занесена в систему для работы «Вектора». Поскольку занесение информации производится редакторами проекта, а не авторами курсов, информация может быть неполной или даже частично неверной. Если Вы нашли ошибку, напишите нам об этом. См. также подробнее о системе «Вектор» и полный список компетенций.