Geodesic
On the concentration of the independence numbers of random hypergraphs
Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 32-46.

Voir la notice de l'article provenant de la source Math-Net.Ru

The asymptotic behavior of general independence numbers of random hypergraphs for the binomial model is studied. We prove that for some types of parameter variations the distribution of independence numbers is concentrated on two neighboring values.
Keywords: random hypergraph, independence number, second moment method. 
@article{DM_2021_33_4_a3,
     author = {I. O. Denisov and D. A. Shabanov},
     title = {On the concentration of the independence numbers of random hypergraphs},
     journal = {Diskretnaya Matematika},
     pages = {32--46},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_4_a3/}
}
TY  - JOUR
AU  - I. O. Denisov
AU  - D. A. Shabanov
TI  - On the concentration of the independence numbers of random hypergraphs
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 32
EP  - 46
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_4_a3/
LA  - ru
ID  - DM_2021_33_4_a3
ER  - 
%0 Journal Article
%A I. O. Denisov
%A D. A. Shabanov
%T On the concentration of the independence numbers of random hypergraphs
%J Diskretnaya Matematika
%D 2021
%P 32-46
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_4_a3/
%G ru
%F DM_2021_33_4_a3
I. O. Denisov; D. A. Shabanov. On the concentration of the independence numbers of random hypergraphs. Diskretnaya Matematika, Tome 33 (2021) no. 4, pp. 32-46. http://geodesic.mathdoc.fr/item/DM_2021_33_4_a3/

[1] Berge C., Hypergraphs, North-Holland, Amsterdam, 1989 | Zbl

[2] Matula D.W., “On the complete subgraphs of a random graph”, Combinatory Mathematics and its applications, Chapel Hill, 1970, 356–369 | Zbl

[3] Grimmett G., McDiarmid C., “On colouring random graphs”, Math. Proc. Cambr. Phil. Soc., 77 (1975), 313–325 | DOI

[4] Bollobás B., Erdős P., “Cliques in random graphs”, Math. Proc. Cambr. Phil. Soc., 80 (1976), 419–427 | DOI | Zbl

[5] Frieze A., “On the independence number of random graphs”, Discrete Mathematics, 81 (1990), 171–175 | DOI | Zbl

[6] Bayati M., Gamarnik D., Tetali P., “Combinatorial approach to the interpolation method and scaling limits in sparse random graphs”, Ann. Prob., 41:6 (2013), 4080–4015 | DOI

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

[8] Schmidt J. P., “Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number”, Discrete Mathematics, 66 (1987), 259–277 | DOI | Zbl

[9] Shamir E., “Chromatic number of random hypergraphs and associated graphs”, Adv. Comput. Res., 5 (1989), 127–142

[10] 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 | Zbl

[11] Semenov A.S., Shabanov D.A., “General independence sets in random strongly sparse hypergraphs”, Problems Inform. Transmission, 54:1 (2018), 56–69 | DOI | Zbl

[12] Semenov A.S., Shabanov D.A., “Independence numbers of random sparse hypergraphs”, Discrete Math. Appl., 27:4 (2017), 231–245 | DOI | Zbl

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

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