Geodesic
Two-colorings of a random hypergraph
Teoriâ veroâtnostej i ee primeneniâ, Tome 64 (2019) no. 1, pp. 75-97 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is concerned with the study of the threshold probability for the existence of a two-coloring for a special random $k$-uniform hypergraph in a binomial model. The first- and second-moment methods are employed to derive upper and lower estimates for the desired threshold probability.
Keywords: hypergraph, colorings of a hypergraph, $j$-chromatic number. 
@article{TVP_2019_64_1_a4,
     author = {A. S. Semenov},
     title = {Two-colorings of a~random hypergraph},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {75--97},
     year = {2019},
     volume = {64},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2019_64_1_a4/}
}
TY  - JOUR
AU  - A. S. Semenov
TI  - Two-colorings of a random hypergraph
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2019
SP  - 75
EP  - 97
VL  - 64
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TVP_2019_64_1_a4/
LA  - ru
ID  - TVP_2019_64_1_a4
ER  - 
%0 Journal Article
%A A. S. Semenov
%T Two-colorings of a random hypergraph
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2019
%P 75-97
%V 64
%N 1
%U http://geodesic.mathdoc.fr/item/TVP_2019_64_1_a4/
%G ru
%F TVP_2019_64_1_a4
A. S. Semenov. Two-colorings of a random hypergraph. Teoriâ veroâtnostej i ee primeneniâ, Tome 64 (2019) no. 1, pp. 75-97. http://geodesic.mathdoc.fr/item/TVP_2019_64_1_a4/

[1] 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

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

[3] 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

[4] 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

[5] N. Alon, J. H. Spencer, A note on coloring random $k$-sets, Unpublished manuscript, 5 pp. www.cs.tau.ac.il/~nogaa/PDFS/kset2.pdf

[6] D. Achlioptas, Jeong Han Kim, M. Krivelevich, P. Tetali, “Two-coloring random hypergraphs”, Random Structures Algorithms, 20:2 (2002), 249–259 | DOI | MR | Zbl

[7] D. Achlioptas, C. Moore, “Random $k$-SAT: two moments suffice to cross a sharp threshold”, SIAM J. Comput., 36:3 (2005), 740–762 | DOI | MR | Zbl

[8] A. Coja-Oghlan, L. Zdeborová, “The condensation transition in random hypergraph $2$-coloring”, Proceedings of the 23rd annual ACM–SIAM symposium on discrete algorithms, ACM, New York, 2012, 241–250 | MR

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

[10] H. Hatami, M. Molloy, “Sharp thresholds for constraint satisfaction problems and homomorphisms”, Random Structures Algorithms, 33:3 (2008), 310–332 | DOI | MR | Zbl