RUS  ENG
Full version
JOURNALS // Doklady Rossijskoj Akademii Nauk. Mathematika, Informatika, Processy Upravlenia // Archive

Dokl. RAN. Math. Inf. Proc. Upr., 2020 Volume 494, Pages 30–34 (Mi danma112)

This article is cited in 1 paper

MATHEMATICS

On the chromatic numbers of random hypergraphs

Yu. A. Demidovicha, D. A. Shabanovabc

a Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow oblast, Russian Federation
b Lomonosov Moscow State University, Moscow, Russian Federation
c National Research University "Higher School of Economics", Moscow, Russian Federation

Abstract: The asymptotic behavior of the chromatic number of the binomial random hypergraph $H(n,k,p)$ is studied in the case when $k\ge4$ 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.

UDC: 519.174, 519.179.1, 519.179.4

Presented: A. N. Shiryaev
Received: 26.11.2019
Revised: 26.11.2019
Accepted: 23.06.2020

DOI: 10.31857/S2686954320050331


 English version:
Doklady Mathematics, 2020, 102:2, 380–383

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025