О структуре множества полноцветных раскрасок случайного гиперграфа

Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2023. Т. 512. № 1. С. 52–57.

Tiapkin D., Shabanov D. A.

The paper deals with the structure of the set of panchromatic colorings with three colors of a random hypergraph in the uniform model $H(n,k,m)$. It is well known that the property of the existence of a panchromatic coloring with given number of colors $r$ has the sharp threshold, i.e. there exists the threshold value $\widehat{m}_r=\widehat{m}_r(n)$ such that for any $\varepsilon>0$, if $m\leqslant (1-\varepsilon)\widehat{m}_r$ then the random hypergraph $H(n,k,m)$ admits this coloring with probability tending to 1, but if $m\geqslant (1+\varepsilon)\widehat{m}_r$ then, vice versa, it does not admit this coloring with probability tending to 1. We study the algorithmic threshold for the property of panchromatic coloring with three colors and prove that if the parameter $m$ is slightly less than $\widehat{m}_3$, then the set of panchromatic 3-colorings of $H(n,k,m)$ although it is not empty with a probability tending to 1, but at the same time it obeys the shattering effect, first described in the work of D. Achlioptas and A. Coja-Oghlan in 2008.

Keywords: случайные гиперграфы, раскраски гиперграфов, panchromatic colorings, random hypergraphs, Colorings of hypergraphs, полноцветные раскраски, shattering, шаттеринг