Geodesic
On two limit values of the chromatic number of a random hypergraph
Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 2, pp. 223-246 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{TVP_2022_67_2_a1,
     author = {Yu. A. Demidovich and D. A. Shabanov},
     title = {On two limit values of the chromatic number of a~random hypergraph},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {223--246},
     year = {2022},
     volume = {67},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2022_67_2_a1/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
AU  - D. A. Shabanov
TI  - On two limit values of the chromatic number of a random hypergraph
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2022
SP  - 223
EP  - 246
VL  - 67
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TVP_2022_67_2_a1/
LA  - ru
ID  - TVP_2022_67_2_a1
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%A D. A. Shabanov
%T On two limit values of the chromatic number of a random hypergraph
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2022
%P 223-246
%V 67
%N 2
%U http://geodesic.mathdoc.fr/item/TVP_2022_67_2_a1/
%G ru
%F TVP_2022_67_2_a1
Yu. A. Demidovich; D. A. Shabanov. On two limit values of the chromatic number of a random hypergraph. Teoriâ veroâtnostej i ee primeneniâ, Tome 67 (2022) no. 2, pp. 223-246. http://geodesic.mathdoc.fr/item/TVP_2022_67_2_a1/

[1] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp. | DOI | MR | Zbl

[2] S. Janson, T. Łuczak, A. Rucinski, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley Sons], New York, 2000, xii+333 pp. | DOI | MR | Zbl

[3] A. Frieze, M. Karoński, Introduction to random graphs, Cambridge Univ. Press, Cambridge, 2016, xvii+464 pp. | DOI | MR | Zbl

[4] B. Bollobás, “The chromatic number of random graphs”, Combinatorica, 8:1 (1988), 49–55 | DOI | MR | Zbl

[5] C. McDiarmid, “On the chromatic number of random graphs”, Random Structures Algorithms, 1:4 (1990), 435–442 | DOI | MR | Zbl

[6] K. Panagiotou, A. Steger, “A note on the chromatic number of a dense random graph”, Discrete Math., 309:10 (2009), 3420–3423 | DOI | MR | Zbl

[7] N. Fountoulakis, R. J. Kang, C. McDiarmid, “The $t$-stability number of a random graph”, Electron. J. Combin., 17:1 (2010), R59, 29 pp. | DOI | MR | Zbl

[8] A. Heckel, “The chromatic number of dense random graphs”, Random Structures Algorithms, 53:1 (2018), 140–182 | DOI | MR | Zbl

[9] T. Łuczak, “A note on the sharp concentration of the chromatic number of random graphs”, Combinatorica, 11:3 (1991), 295–297 | DOI | MR | Zbl

[10] N. Alon, M. Krivelevich, “The concentration of the chromatic number of random graphs”, Combinatorica, 17:3 (1997), 303–313 | DOI | MR | Zbl

[11] D. Achlioptas, A. Naor, “The two possible values of the chromatic number of a random graph”, Ann. of Math. (2), 162:3 (2005), 1335–1351 | DOI | MR | Zbl

[12] A. Coja-Oghlan, D. Vilenchik, “The chromatic number of random graphs for most average degrees”, Int. Math. Res. Not. IMRN, 2016:19 (2016), 5801–5859 | DOI | MR | Zbl

[13] A. Coja-Oghlan, “Upper-bounding the $k$-colorability threshold by counting covers”, Electron. J. Combin., 20:3 (2013), P32, 28 pp. | DOI | MR | Zbl

[14] A. Coja-Oghlan, K. Panagiotou, A. Steger, “On the chromatic number of random graphs”, J. Combin. Theory Ser. B, 98:5 (2008), 980–993 | DOI | MR | Zbl

[15] S. Kargaltsev, D. Shabanov, T. Shaikheeva, “Two values of the chromatic number of a sparse random graph”, Acta Math. Univ. Comenian. (N.S.), 88:3 (2019), 849–854 | MR

[16] J. Schmidt-Pruzan, E. Shamir, E. Upfal, “Random hypergraph coloring algorithms and the weak chromatic number”, J. Graph Theory, 9:3 (1985), 347–362 | DOI | MR | Zbl

[17] E. Shamir, “Chromatic number of random hypergraphs and associated graphs”, Randomness and computation, Adv. Comput. Res., 5, JAI Press, Inc., Greenwich, CT–London, 1989, 127–142

[18] M. Krivelevich, B. Sudakov, “The chromatic numbers of random hypergraphs”, Random Structures Algorithms, 12:4 (1998), 381–403 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[19] M. Dyer, A. Frieze, C. Greenhill, “On the chromatic number of a random hypergraph”, J. Combin. Theory Ser. B, 113 (2015), 68–122 | DOI | MR | Zbl

[20] D. A. Shabanov, “On the concentration of the chromatic number of a random hypergraph”, Dokl. Math., 96:1 (2017), 321–325 | DOI | MR | Zbl

[21] D. A. Shabanov, “Estimating the $r$-colorability threshold for a random hypergraph”, Discrete Appl. Math., 282 (2020), 168–183 | DOI | MR | Zbl

[22] P. Ayre, A. Coja-Oghlan, C. Greenhill, “Hypergraph coloring up to condensation”, Random Structures Algorithms, 54:4 (2019), 615–652 | DOI | MR | Zbl

[23] D. Kravtsov, N. Krokhmal, D. Shabanov, “Panchromatic $3$-colorings of random hypergraphs”, European J. Combin., 78 (2019), 28–43 | DOI | MR | Zbl

[24] D. A. Kravtsov, N. E. Krokhmal, D. A. Shabanov, “Panchromatic colorings of random hypergraphs”, Discrete Math. Appl., 31:1 (2021), 19–41 | DOI | DOI | MR | Zbl

[25] A. S. Semenov, “Two-colorings of a random hypergraph”, Theory Probab. Appl., 64:1 (2019), 59–77 | DOI | DOI | MR | Zbl

[26] A. Semenov, D. Shabanov, “On the weak chromatic number of random hypergraphs”, Discrete Appl. Math., 276 (2020), 134–154 | DOI | MR | Zbl

[27] A. E. Balobanov, D. A. Shabanov, “On the strong chromatic number of a random $3$-uniform hypergraph”, Discrete Math., 344:3 (2021), 112231, 16 pp. | DOI | MR | Zbl

[28] A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Combin., 25:4 (2018), P4.52, 16 pp. | DOI | MR | Zbl

[29] J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | MR | Zbl

[30] S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random Kneser graphs”, Acta Math. Univ. Comenian. (N.S.), 88:3 (2019), 861–865 | MR