Аннотация:
Доклад посвящен задаче о сильном хроматическом числе случайного гиперграфа в биномиальной модели $H(n,k,p)$. Напомним, что сильным хроматическим числом гиперграфа $H$, $\chi_{str}(H)$, называется такое наименьшее число $q$, что существует раскраска множества вершин гиперграфа в $q$ цветов, в которой в каждом ребре все его вершины покрашены в разные цвета (сильная раскраска). Сильное хроматическое число для плотного случая, т.е., когда $pn^{k-1}\to+\infty$, было хорошо изучено в работе М. Кривелевича и Б. Судакова (1998). Мы же концентрируемся на так называемом разреженном случае, когда $p{n\choose k}=cn$ и $c>0$ не зависит от $n$. Известно, что в такой ситуации сильное хроматическое число $H(n,k,p)$ ограничено. В докладе будут представлены новые оценки пороговой вероятности для свойства сильной $q$-раскрашиваемости случайного $k$-однородного гиперграфа и, как следствие, получение результатов о концентрации его значений в одном или двух соседних значениях. Доклад основан на совместной работе с Т. Г. Матвеевой и А. Э. Хузиевой.
|
