Метод случайной раскраски гиперграфов в задачах экстремальной комбинаторики

В докладе будет рассказано о задачах теории раскрасок гиперграфов, которые находятся на стыке экстремальной и вероятностной комбинаторики. Данные задачи тесно связаны с классическими проблемами теории Рамсея (например, со знаменитой теоремой Рамсея), экстремальной теории множеств (проблема Турана и задачи о покрытии) и комбинаторной теории чисел (теорема Ван дер Вардена об арифметических прогрессиях).
Как и во многих других проблемах, наилучшие результаты в подобных задачах получаются применением различных вероятностных техник. Более того, именно в ходе исследования вопроса о существовании правильных раскрасок гиперграфов Л. Ловасом была доказана знаменитая Локальная лемма —утверждение о положительности вероятности одновременного выполнения конечного набора событий в условиях «малого числа зависимостей». В дальнейшем эта чисто вероятностная лемма нашла применение во многих других задачах комбинаторики, теории чисел, теоретической информатики и теории алгоритмов.
В докладе мы подробно остановимся на методе случайной раскраски, который на сегодняшний день является одним из наиболее эффективных способов получения оценок различных экстремальных величин, возникающих в теории раскрасок гиперграфов.