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/(nk) for positive fixed c. Estimates of the form c1(r,k)<c<c2(r,k) for the parameter c are found such that the difference c2(r,k)−c1(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.
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
This publication is cited in the following 5 articles:
M. M. Koshelev, D. A. Shabanov, T. M. Shaikheeva, “Porogovye veroyatnosti dlya raskrasok sluchainykh gipergrafov”, UMN, 80:1(481) (2025), 161–162
D. N. Tyapkin, D. A. Shabanov, “On the structure of the set of panchromatic colorings of a random hypergraph”, Dokl. Math., 108:1 (2023), 286–290
Yu. A. Demidovich, D. A. Shabanov, “On two limit values of the chromatic number of a random hypergraph”, Theory Probab. Appl., 67:2 (2022), 175–193
D. A. Shabanov, T. M. Shaikheeva, “The List-Chromatic Number of Complete Multipartite Hypergraphs and Multiple Covers by Independent Sets”, Math. Notes, 107:3 (2020), 499–508
Yu. A. Demidovich, D. A. Shabanov, “On the chromatic numbers of random hypergraphs”, Dokl. Math., 102:2 (2020), 380–383