|
This article is cited in 1 scientific paper (total in 1 paper)
On two limit values of the chromatic number of a random hypergraph
Yu. A. Demidovicha, D. A. Shabanovbc a Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
b Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
c Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
The limit concentration of the values of the chromatic number of the random
hypergraph $H(n,k,p)$ in the binomial model is studied. It is proved that,
for a fixed $k\ge 3$ and with not too rapidly increasing $n^{k-1}p$, the
chromatic number of the hypergraph $H(n,k,p)$ lies, with probability tending
to $1$, in the set of two consecutive values. Moreover, it is shown that,
under slightly stronger constraints on the growth of $n^{k-1}p$, these
values can be explicitly evaluated as functions of $n$ and $p$.
Keywords:
random hypergraph, chromatic number, second moment method.
Received: 18.11.2020 Revised: 22.10.2021 Accepted: 24.10.2021
Citation:
Yu. A. Demidovich, D. A. Shabanov, “On two limit values of the chromatic number of a random hypergraph”, Teor. Veroyatnost. i Primenen., 67:2 (2022), 223–246; Theory Probab. Appl., 67:2 (2022), 175–193
Linking options:
https://www.mathnet.ru/eng/tvp5458https://doi.org/10.4213/tvp5458 https://www.mathnet.ru/eng/tvp/v67/i2/p223
|
Statistics & downloads: |
Abstract page: | 271 | Full-text PDF : | 39 | References: | 30 | First page: | 16 |
|