Panchromatic colorings of random hypergraphs
Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 84-113
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
random hypergraph, panchromatic colorings, threshold probabilities, second moment method.
@article{DM_2019_31_2_a7,
author = {D. A. Kravtsov and N. E. Krokhmal and D. A. Shabanov},
title = {Panchromatic colorings of random hypergraphs},
journal = {Diskretnaya Matematika},
pages = {84--113},
publisher = {mathdoc},
volume = {31},
number = {2},
year = {2019},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/}
}
D. A. Kravtsov; N. E. Krokhmal; D. A. Shabanov. Panchromatic colorings of random hypergraphs. Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 84-113. http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/