Аннотация:
Случайный граф в биномиальной модели 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}). Кроме того, мы обсудим аналогичные вопросы для гиперграфов.
|
