|
This article is cited in 4 scientific papers (total in 4 papers)
Panchromatic colorings of random hypergraphs
D. A. Kravtsova, N. E. Krokhmala, D. A. Shabanovbac a Lomonosov Moscow State University
b MIPT
c National Research University "Higher School of Economics", Moscow
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.
Received: 11.02.2018
Citation:
D. A. Kravtsov, N. E. Krokhmal, D. A. Shabanov, “Panchromatic colorings of random hypergraphs”, Diskr. Mat., 31:2 (2019), 84–113; Discrete Math. Appl., 31:1 (2021), 19–41
Linking options:
https://www.mathnet.ru/eng/dm1504https://doi.org/10.4213/dm1504 https://www.mathnet.ru/eng/dm/v31/i2/p84
|
Statistics & downloads: |
Abstract page: | 387 | Full-text PDF : | 38 | References: | 37 | First page: | 16 |
|