Abstract:
The asymptotic behavior of the chromatic number of the binomial random hypergraph H(n,k,p) is studied in the case when k⩾4 is fixed, n tends to infinity, and p=p(n) is a function. If p=p(n) does not decrease too slowly, we prove that the chromatic number of H(n,k,p) is concentrated in two or three consecutive values, which can be found explicitly as functions of n, p and k.
Keywords:
random hypergraph, chromatic number, second moment method.
Citation:
Yu. A. Demidovich, D. A. Shabanov, “On the chromatic numbers of random hypergraphs”, Dokl. RAN. Math. Inf. Proc. Upr., 494 (2020), 30–34; Dokl. Math., 102:2 (2020), 380–383
\Bibitem{DemSha20}
\by Yu.~A.~Demidovich, D.~A.~Shabanov
\paper On the chromatic numbers of random hypergraphs
\jour Dokl. RAN. Math. Inf. Proc. Upr.
\yr 2020
\vol 494
\pages 30--34
\mathnet{http://mi.mathnet.ru/danma112}
\crossref{https://doi.org/10.31857/S2686954320050331}
\zmath{https://zbmath.org/?q=an:1478.05134}
\elib{https://elibrary.ru/item.asp?id=44344643}
\transl
\jour Dokl. Math.
\yr 2020
\vol 102
\issue 2
\pages 380--383
\crossref{https://doi.org/10.1134/S1064562420050312}
Linking options:
https://www.mathnet.ru/eng/danma112
https://www.mathnet.ru/eng/danma/v494/p30
This publication is cited in the following 1 articles:
Yury A. Demidovich, Dmitry A. Shabanov, Springer Proceedings in Mathematics & Statistics, 371, Recent Developments in Stochastic Methods and Applications, 2021, 190