Abstract:
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 $\hat m_r=\hat m_r(n)$ such that for any $\varepsilon>0$, if $m\le(1-\varepsilon)\hat m_r$ then the random hypergraph $H(n,k,m)$ admits this coloring with probability tending to $1$, but if $m\ge(1+\varepsilon)\hat 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 $\hat 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:random hypergraph, colorings of hypergraphs, panchromatic colorings, shattering.
UDC:519.179.1, 519.179.4
Presented:A. N. Shiryaev Received: 30.03.2023 Revised: 05.05.2023 Accepted: 20.05.2023