Abstract:
The paper deals with the study of the probability threshold for the property of strong colorability with given number of colors of the random $k$-uniform hypergraph in the binomial model $H(n,k,p)$. A vertex coloring of a hypergraph is said to be strong if any edge does not have two vertices of the same color under it. We study the problem of finding the sharp probability threshold of the existence of a strong coloring with $q$ colors for $H(n,k,p)$. By using the second moment method we obtain very tight bounds for this value provided that $q$ is large enough in comparison with $k$.
Keywords:random hypergraph, colorings of hypergraphs, probability thresholds, strong chromatic number, second moment method.
UDC:519.174, 519.179.1, 519.179.4
Presented:A. N. Shiryaev Received: 15.11.2021 Revised: 15.11.2021 Accepted: 20.12.2021