Laboratory of Mathematical Logic at PDMI

Пятница, 9 сентября, ауд. 106. Начало в 18:00.

Докладчик: Д.А. Шабанов (МГУ).

Тема: Экстремальные задачи о раскрасках гиперграфов, их приложения в теории графов и комбинаторной теории чисел.

Abstract

В докладе будет рассказано о задачах теории раскрасок гиперграфов, которые находятся на стыке экстремальной и вероятностной комбинаторики. Данные задачи тесно связаны с классическими проблемами теории Рамсея (например, со знаменитой теоремой Рамсея), экстремальной теории множеств (проблема Турана и задачи о покрытии) и комбинаторной теории чисел (теорема Ван дер Вардена об арифметических прогрессиях).

Рассматриваемый класс проблем берет свое начало с задачи Эрдеша и Хайнала, которые поставили вопрос о нахождении минимально возможного количества ребер n-равномерного гиперграфа с хроматическим числом больше r. В докладе будет рассказано об обобщениях данной проблемы для различных классов гиперграфов (простых и h-простых гиперграфов, гиперграфов с большим обхватом), а также о постановках подобных проблем для некоторых других видов раскрасок (предписанных и полноцветных).

Особое внимание будет уделено оценкам максимальной степени вершины гиперграфа в классе n-равномерных гиперграфов с большим хроматическим числом. Подобные оценки, а также вероятностные методы их получения, находят самое активное применение при обосновании нижних оценок в теоремах Рамсея и Ван дер Вардена.