Geodesic
On the chromatic numbers of random hypergraphs
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 30-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{DANMA_2020_494_a6,
     author = {Yu. A. Demidovich and D. A. Shabanov},
     title = {On the chromatic numbers of random hypergraphs},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {30--34},
     year = {2020},
     volume = {494},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2020_494_a6/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
AU  - D. A. Shabanov
TI  - On the chromatic numbers of random hypergraphs
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 30
EP  - 34
VL  - 494
UR  - http://geodesic.mathdoc.fr/item/DANMA_2020_494_a6/
LA  - ru
ID  - DANMA_2020_494_a6
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%A D. A. Shabanov
%T On the chromatic numbers of random hypergraphs
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2020
%P 30-34
%V 494
%U http://geodesic.mathdoc.fr/item/DANMA_2020_494_a6/
%G ru
%F DANMA_2020_494_a6
Yu. A. Demidovich; D. A. Shabanov. On the chromatic numbers of random hypergraphs. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 30-34. http://geodesic.mathdoc.fr/item/DANMA_2020_494_a6/

[1] Luczak T., “A Note on the Sharp Concentration of the Chromatic Number of Random Graphs”, Combinatorica, 11:3 (1991), 295–297 | DOI | MR | Zbl

[2] Alon N., Krivelevich M., “The Concentration of the Chromatic Number of Random Graphs”, Combinatorica, 17:3 (1997), 303–313 | DOI | MR | Zbl

[3] Achlioptas D., Naor A., “The Two Possible Values of the Chromatic Number of a Random Graph”, Annals of Mathematics, 162:3 (2005), 1335–1351 | DOI | MR | Zbl

[4] Coja-Oghlan A., Vilenchik D., “The Chromatic Number of Random Graphs for Most Average Degrees”, International Mathematics Research Notices, 2016:19 (2015), 5801–5859 | DOI | MR

[5] Coja-Oghlan A., “Upper-Bounding the k-Colorability Threshold by Counting Covers”, Electronic J. Combinatorics, 20:3 (2013), 32 | DOI | MR

[6] Coja-Oghlan A., Panagiotou K., Steger A., “On the Chromatic Number of Random Graphs”, J. Combinatorial Theory, Ser. B, 98 (2008), 980–993 | DOI | MR | Zbl

[7] Kargaltsev S.A., Shabanov D.A., Shaikheeva T.M., “Two Values of the Chromatic Number of a Sparse Random Graph”, Acta Mathematica Universitatis Comenianae, 88:3 (2019), 849–854 | MR

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

[9] Dyer M., Frieze A., Greenhill C., “On the Chromatic Number of a Random Hypergraph”, J. Combinatorial Theory, Ser. B, 113 (2015), 68–122 | DOI | MR | Zbl

[10] Shabanov D.A., “O kontsentratsii khromaticheskogo chisla sluchainogo gipergrafa”, DAN, 475:1 (2017), 24–28 | Zbl

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

[12] Kupavskii A., “Random Kneser Graphs and Hypergraphs”, Electronic J. Combinatorics, 25:4 (2018), 4.52 | DOI | MR | Zbl

[13] Kravtsov D.A., Krokhmal N.E., Shabanov D.A., “Panchromatic 3-colorings of Random Hypergraphs”, European J. Combinatorics, 78 (2019), 28–43 | DOI | MR

[14] Kravtsov D.A., Krokhmal N.E., Shabanov D.A., “Polnotsvetnye raskraski sluchainykh gipergrafov”, Diskretnaya matematika, 31:2 (2019), 84–113 | DOI

[15] Semenov A.S., “Dvukhtsvetnye raskraski sluchainogo gipergrafa”, Teoriya veroyatnostei i ee primeneniya, 64:1 (2019), 75–97 | DOI | MR | Zbl