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