Panchromatic colorings of random hypergraphs

D. A. Kravtsov ; N. E. Krokhmal ; D. A. Shabanov

Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 84-113

Résumé

We study the threshold probability for the existence of a panchromatic coloring with $r$ colors for a random $k$-homogeneous hypergraph in the binomial model $ H (n, k, p) $, that is, a coloring such that each edge of the hypergraph contains the vertices of all $r$ colors. It is shown that this threshold probability for fixed $r$ and increasing $n$ corresponds to the sparse case, i. e. the case $p = cn/{n \choose k}$ for positive fixed $c$. Estimates of the form $ c_1 (r, k)$ for the parameter $c$ are found such that the difference $ c_2 (r, k) -c_1 (r, k) $ converges exponentially fast to zero if $r$ is fixed and $k$ tends to infinity.

Détail

Keywords: random hypergraph, panchromatic colorings, threshold probabilities, second moment method.