RUS  ENG
Полная версия
СЕМИНАРЫ

Большой семинар кафедры теории вероятностей МГУ
12 сентября 2018 г. 16:45, г. Москва, ГЗ МГУ, ауд. 12-24


Предельные теоремы в теории случайных гиперграфов

А. С. Семенов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

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


© МИАН, 2024