RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 2022 Volume 67, Issue 2, Pages 223–246 (Mi tvp5458)

This article is cited 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

DOI: 10.4213/tvp5458


 English version:
Theory of Probability and its Applications, 2022, 67:2, 175–193

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025