TY - JOUR
T1 - ON TWO LIMIT VALUES OF THE CHROMATIC NUMBER OF A RANDOM HYPERGRAPH
AU - Demidovich, Yu A.
AU - Shabanov, D. A.
N1 - Funding Information:
∗Received by the editors November 18, 2020; revised October 22, 2021. Published electronically August 4, 2022. This research was carried out with the financial support of the Russian Foundation for Basic Research (grant 20-31-70039). The second author was supported by the grant of the President of Russian Federation MD-1562.2020.1. Originally published in the Russian journal Teoriya Veroyatnostei i ee Primeneniya, 67 (2022), pp. 223–246. https://doi.org/10.1137/S0040585X97T990861 †Department of Discrete Mathematics and Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (National Research University), Dolgo-prudnyi, Moscow Region, Russia ([email protected]).
Funding Information:
This research was carried out with the financial support of the Russian Foundation for Basic Research (grant 20-31-70039). The second author was supported by the grant of the President of Russian Federation MD-1562.2020.1. Originally published in the Russian journal Teoriya Veroyatnostei i ee Primeneniya, 67 (2022), pp. 223–246.
Publisher Copyright:
© by SIAM. Unauthorized reproduction of this article is prohibited.
PY - 2022
Y1 - 2022
N2 - The limit concentration of the values of the chromatic number of the random hyper-graph H(n, k, p) in the binomial model is studied. It is proved that, for a fixed k ⩾ 3 and with not too rapidly increasing nk−1p, 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 nk−1p, these values can be explicitly evaluated as functions of n and p.
AB - The limit concentration of the values of the chromatic number of the random hyper-graph H(n, k, p) in the binomial model is studied. It is proved that, for a fixed k ⩾ 3 and with not too rapidly increasing nk−1p, 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 nk−1p, these values can be explicitly evaluated as functions of n and p.
KW - chromatic number
KW - random hypergraph
KW - second moment method
UR - http://www.scopus.com/inward/record.url?scp=85161851600&partnerID=8YFLogxK
U2 - 10.1137/S0040585X97T990861
DO - 10.1137/S0040585X97T990861
M3 - Article
AN - SCOPUS:85161851600
SN - 0040-585X
VL - 67
SP - 175
EP - 193
JO - Theory of Probability and its Applications
JF - Theory of Probability and its Applications
IS - 2
ER -