Семинар МЛ АТиП: "Предельная концентрация значений хроматического числа случайного графа Эрдеша-Реньи"

Докладчик: Дмитрий Шабанов (ведущий научный сотрудник МЛ АТиП)

Случайный граф в биномиальной модели G(n,p) (случайный граф в модели Эрдеша--Реньи) начиная с конца 50-х годов прошлого века является одним из основных объектов изучения вероятностной комбинаторики. И одним из первых вопросов, поставленных П. Эрдешем был вопрос об асимптотическом поведении хроматического числа случайного графа G(n,p). В 1991 году Т. Лучаком было доказано, что при не слишком быстро растущем произведении np хроматическое число случайного графа сконцентрировано в двух соседних значениях, которые, однако, были неизвестны. Мы представим свои последние результаты, в которых эти значения были найдены для почти всех функций p=p(n) вплоть до o(n^{-3/4}).

Идентификатор конференции: 895 5046 0770

Код доступа необходимо запросить у организаторов