О предельном распределении хроматического числа случайного графа

Случайный граф в биномиальной модели $G(n,p)$ (случайный граф в модели Эрдеша–Реньи) начиная с конца 50-х годов прошлого века является основным объектом изучения вероятностной комбинаторики. И одним из первых вопросов, поставленных П. Эрдешем, был вопрос об асимптотическом поведении хроматического числа случайного графа $G(n,1/2)$, т.е. о “типичном” хроматическом числе графа на $n$ вершинах. Данная проблема привлекала внимание всех ведущих мировых исследователей по вероятностной комбинаторике, но только в 1988 году Б. Боллобашем был установлен закон больших чисел для $G(n,1/2)$. Предложенный им подход, основанный на применении неравенств больших уклонений для мартингалов, оказался весьма универсальным и позволил начать изучение хроматического числа $G(n,p)$ при различных соотношениях между параметрами $p=p(n)$ и $n$. Оказывается, при не слишком быстро растущем произведении $np$ хроматическое число случайного графа сконцентрировано в двух соседних значениях, которые однако были неизвестны. Мы представим свои последние результаты, в которых эти значения были найдены для почти всех функций $p=p(n)$ вплоть до $o(n^{-3/4})$. Кроме того, мы обсудим аналогичные вопросы для проблемы RANDOM $k$-SAT о выполнимости случайной булевой функции и ее некоторые естественные обобщения, связанные с полноцветными раскрасками гиперграфов.