Geodesic
Random constructions of hypergraphs with large girth and without panchromatic colorings
Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2020) no. 1, pp. 269-283.

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

We give probabilistic constructions of hypergraphs with large girth that do not admit panchromatic colorings. We prove new upper bounds on the minimal values of the number of edges and the maximum vertex degree in such hypergraphs. 
@article{FPM_2020_23_1_a15,
     author = {A. E. Khuzieva},
     title = {Random constructions of hypergraphs with large girth and without panchromatic colorings},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {269--283},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a15/}
}
TY  - JOUR
AU  - A. E. Khuzieva
TI  - Random constructions of hypergraphs with large girth and without panchromatic colorings
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2020
SP  - 269
EP  - 283
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a15/
LA  - ru
ID  - FPM_2020_23_1_a15
ER  - 
%0 Journal Article
%A A. E. Khuzieva
%T Random constructions of hypergraphs with large girth and without panchromatic colorings
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2020
%P 269-283
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a15/
%G ru
%F FPM_2020_23_1_a15
A. E. Khuzieva. Random constructions of hypergraphs with large girth and without panchromatic colorings. Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2020) no. 1, pp. 269-283. http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a15/

[1] Raigorodskii A. M., Shabanov D. A., “Zadacha Erdesha–Khainala o raskraskakh gipergrafov, ee obobscheniya i smezhnye problemy”, UMN, 66:5 (2011), 109–182 | MR | Zbl

[2] Rozovskaya A. P., Shabanov D. A., “Ekstremalnye zadachi dlya polnotsvetnykh raskrasok ravnomernykh gipergrafov”, Diskret. matem., 24:2 (2012), 104–122 | MR | Zbl

[3] Khuzieva A. E., Shabanov D. A., “Ob odnorodnykh gipergrafakh s bolshim obkhvatom i bolshim khromaticheskim chislom”, Diskret. matem., 27:2 (2015), 112–133 | MR | Zbl

[4] Khuzieva A. E., Shabanov D. A., “Kolichestvennye otsenki kharakteristik v gipergrafakh s bolshim obkhvatom i bolshim khromaticheskim chislom”, Matem. zametki, 98:6 (2015), 948–951 | MR | Zbl

[5] Shabanov D. A., “Ekstremalnye zadachi dlya raskrasok ravnomernykh gipergrafov”, Izv. RAN. Ser. matem., 71:6 (2007), 183–222 | MR | Zbl

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

[7] Akolzin I. A., Shabanov D. A., “Colorings of hypergraphs with large number of colors”, Discrete Math., 339:12 (2016), 3020–3031 | DOI | MR | Zbl

[8] Cherkashin D., “A note on panchromatic colorings”, Discrete Math., 341:3 (2018), 652–657 | DOI | MR | Zbl

[9] Erdős P., Lovász L., “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, 10 (1973), 609–627 | MR

[10] Frieze A., Mubayi D., “Coloring simple hypergraphs”, J. Combin. Theory Ser. B, 103 (2013), 767–794 | DOI | MR

[11] Kostochka A. V., Rödl V., “Constructions of sparse uniform hypergraphs with high chromatic number”, Random Struct. Algorithms, 36:1 (2010), 46–56 | DOI | MR | Zbl

[12] Kozik J., Shabanov D. A., “Improved algorithms for colorings of simple hypergraphs and applications”, J. Combin. Theory Ser. B, 116 (2016), 312–332 | DOI | MR | Zbl

[13] Kupavskii A. B., Shabanov D. A., “Colourings of uniform hypergraphs with large girth and applications”, Combin. Probab. Comput., 27:2 (2018), 245–273 | DOI | MR | Zbl

[14] Sauer N., “On the existence of regular $n$-graphs with given girth”, J. Combin. Theory Ser. B, 9 (1970), 144–147 | DOI | MR | Zbl