Аннотация:
Доклад посвящен одному из центральных направлений вероятностной комбинаторики — теории случайных гиперграфов. Изучается классическая биномиальная модель случайного гиперграфа $H(n,k,p)$, в которой каждое $k$-подмножество (ребро) $n$-элементного множества вершин включается в случайный гиперграф независимо от других с вероятностью $p$. В докладе будет коротко освещена предыстория проводимых исследований и рассказано о новых результатах, полученных автором.
Тематически доклад будет состоять из двух частей. В первой части доклада будет обсуждаться предельное поведение числа независимости случайного гиперграфа $H(n,k,p)$ и его параметрических обобщений, чисел $j$-независимости. Наиболее незавершенным случаем в этой области является случай разреженного случайного гиперграфа, когда математическое ожидание числа ребер линейно по отношению к числу его вершин. Здесь автором установлены законы больших чисел для исследуемых величин в виде теоремы существования. Для сильно разреженного случая удается и указать явный вид предельной константы.
Вторая большая тема исследований посвящена раскраскам случайных гиперграфов.
Здесь изучается предельное распределение $j$-хроматического числа случайного
гиперграфа в разреженном случае. Первый новый результат дает очень точные
оценки пороговой вероятности для свойства $j$-хроматическое число
равно двум. Второй новый результат в этом направлении устанавливает
предельное распределение $j$-хроматического числа случайного гиперграфа
$H(n,k,p)$ в частном случае $j=k-2$. В частности, показано, что множество
предельных значений либо одноточечное, либо состоит из двух соседних
значений, которые могут быть найдены явно.
|
