Abstract:
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<k$ 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)<c<c_2 (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.
Fulltext:
PDF file (627 kB)
