I. O. Denisov, D. A. Shabanov, “On the concentration of values of <nobr>$j$</nobr>-chromatic numbers of random hypergraphs”, Dokl. RAN. Math. Inf. Proc. Upr., 2023, Volume 509,Pages <nobr>28

MATHEMATICS

On the concentration of values of $j$-chromatic numbers of random hypergraphs

I. O. Denisov^a, D. A. Shabanov^bc

^a Lomonosov Moscow State University, Moscow, Russia
^b HSE University, Moscow, Russia
^c Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow oblast, Russia

Abstract: The limit distribution of the $j$-chromatic numbers of a random $k$-uniform hypergraph in the binomial model $H(n,k,p)$ is studied. We consider the sparse case when the expected number of edges is a linear function of the number of vertices n, i.e., is equal to $cn$ for $c>0$ independent of $n$. We prove that, for all large enough values of $c$, the $j$-chromatic number of $H(n,k,p)$ is concentrated in one or two consecutive values with probability tending to $1$.

Keywords: random hypergraph, colorings of hypergraphs, $j$-chromatic number, probability thresholds, second moment method.

UDC: 519.179.1

Presented: A. N. Shiryaev
Received: 15.12.2022
Revised: 20.12.2022
Accepted: 28.12.2022

DOI: 10.31857/S2686954322600756