Geodesic
Panchromatic colorings of random hypergraphs
Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 84-113.

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

We study the threshold probability for the existence of a panchromatic coloring with $r$ colors for a random $k$-homogeneous hypergraph in the binomial model $ H (n, k, p) $, that is, a coloring such that each edge of the hypergraph contains the vertices of all $r$ colors. It is shown that this threshold probability for fixed $r$ and increasing $n$ corresponds to the sparse case, i. e. the case $p = cn/{n \choose k}$ for positive fixed $c$. Estimates of the form $ c_1 (r, k)$ for the parameter $c$ are found such that the difference $ c_2 (r, k) -c_1 (r, k) $ converges exponentially fast to zero if $r$ is fixed and $k$ tends to infinity.
Keywords: random hypergraph, panchromatic colorings, threshold probabilities, second moment method. 
@article{DM_2019_31_2_a7,
     author = {D. A. Kravtsov and N. E. Krokhmal and D. A. Shabanov},
     title = {Panchromatic colorings of random hypergraphs},
     journal = {Diskretnaya Matematika},
     pages = {84--113},
     publisher = {mathdoc},
     volume = {31},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/}
}
TY  - JOUR
AU  - D. A. Kravtsov
AU  - N. E. Krokhmal
AU  - D. A. Shabanov
TI  - Panchromatic colorings of random hypergraphs
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 84
EP  - 113
VL  - 31
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/
LA  - ru
ID  - DM_2019_31_2_a7
ER  - 
%0 Journal Article
%A D. A. Kravtsov
%A N. E. Krokhmal
%A D. A. Shabanov
%T Panchromatic colorings of random hypergraphs
%J Diskretnaya Matematika
%D 2019
%P 84-113
%V 31
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/
%G ru
%F DM_2019_31_2_a7
D. A. Kravtsov; N. E. Krokhmal; D. A. Shabanov. Panchromatic colorings of random hypergraphs. Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 84-113. http://geodesic.mathdoc.fr/item/DM_2019_31_2_a7/

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

[2] N. Alon, J. Spencer, “A note on coloring random $k$-sets”, Unpublished manuscript http://www.cs.tau.ac.il/~nogaa/PDFS/kset2.pdf

[3] D. Achlioptas, J.H. Kim, M. Krivelevich, P. Tetali, “Two-colorings random hypergraphs”, Random Struct. Algor., 20:2 (2002), 249–259 | DOI | MR | Zbl

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

[5] A. Coja-Oghlan, L. Zdeborová, “The condensation transition in random hypergraph 2-coloring”, Proc. 23rd Annu. ACM–SIAM Symp. Discr. Algor., SIAM, 2012, 241–250 | MR | Zbl

[6] P. Erdős, L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, Colloq. Math. Soc. J. Bolyai, 10, Amsterdam: North Holland, 1973, 609–627 | MR

[7] A.V. Kostochka, “On a theorem by Erdős, Rubin and Taylor on choosability of complete bipartite graphs”, Electr. J. Comb., 9 (2002) | MR | Zbl

[8] D.A. Shabanov, “On a generalization of Rubin's theorem”, J. Graph Theory, 67:3 (2011), 226–234 | DOI | MR | Zbl

[9] D.A. Kravtsov, N.E. Krokhmal, D.A. Shabanov, “Panchromatic 3-colorings of random hypergraphs”, Eur. J. Combinator., 78 (2019), 28–43 | DOI | MR

[10] D.A. Shabanov, “O suschestvovanii polnotsvetnykh raskrasok dlya ravnomernykh gipergrafov”, Matem. sb., 201:4 (2010), 137–160 | DOI | Zbl

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

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

[13] D. Cherkashin, “Note on panchromatic colorings”, Discrete Mathematics, 341:13 (2018), 652–657 | DOI | MR | Zbl