Geodesic
On some generalizations of the property B problem of an $n$-uniform hypergraph
Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2020) no. 1, pp. 95-122.

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

The extremal problem of hypergraph colorings related to the Erdős–Hajnal property $B$-problem is considered. Let $k$ be a natural number. The problem is to find the value of $m_k(n)$ equal to the minimal number of edges in an $n$-uniform hypergraph that does not admit $2$-colorings of the vertex set such that every edge of the hypergraph contains at least $k$ vertices of each color. In this paper, we obtain new lower bounds for $m_k(n)$. 
@article{FPM_2020_23_1_a5,
     author = {Yu. A. Demidovich},
     title = {On some generalizations of the property {B} problem of an $n$-uniform hypergraph},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {95--122},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a5/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
TI  - On some generalizations of the property B problem of an $n$-uniform hypergraph
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2020
SP  - 95
EP  - 122
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a5/
LA  - ru
ID  - FPM_2020_23_1_a5
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%T On some generalizations of the property B problem of an $n$-uniform hypergraph
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2020
%P 95-122
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a5/
%G ru
%F FPM_2020_23_1_a5
Yu. A. Demidovich. On some generalizations of the property B problem of an $n$-uniform hypergraph. Fundamentalʹnaâ i prikladnaâ matematika, Tome 23 (2020) no. 1, pp. 95-122. http://geodesic.mathdoc.fr/item/FPM_2020_23_1_a5/

[1] Demidovich Yu. A., Raigorodskii A. M., “Dvukhtsvetnye raskraski odnorodnykh gipergrafov”, Matem. zametki, 100:4 (2016), 623–626 | MR | Zbl

[2] Kupavskii A. B., Shabanov D. A., “Raskraski chastichnykh sistem Shteinera i ikh prilozheniya”, Fundament. i prikl. matem., 18:3 (2013), 77–115

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

[4] Rozovskaya A. P., “O dvukhtsvetnykh raskraskakh obschego vida dlya ravnomernykh gipergrafov”, Dokl. RAN, 429:3 (2009), 309–311 | MR | Zbl

[5] Rozovskaya A. P., “Ekstremalnye kombinatornye zadachi dlya dvukhtsvetnykh raskrasok gipergrafov”, Matem. zametki, 90:4 (2011), 584–598 | MR | Zbl

[6] Teplyakov S. M., “Verkhnyaya otsenka v zadache Erdesha–Khainala o raskraske gipergrafa”, Matem. zametki, 93:1 (2013), 148–151 | MR | Zbl

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

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

[9] Shabanov D. A., “Ob odnoi kombinatornoi zadache Erdesha”, Dokl. RAN, 396:2 (2004), 166–169 | MR | Zbl

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

[11] Shabanov D. A., “Randomizirovannye algoritmy raskrasok gipergrafov”, Matem. sb., 199:7 (2008), 139–160 | MR | Zbl

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

[13] Cherkashin D., Kozik J., “A note on random greedy coloring of uniform hypergraphs”, Random Struct. Algorithms, 47:3 (2015), 407–413 | DOI | MR | Zbl

[14] Erd{ő}s P., “On a combinatorial problem”, Nordisk Mat. Tidskr, 11 (1963), 5–10 | MR | Zbl

[15] Erd{ő}s P., “On a combinatorial problem. II”, Acta Math. Acad. Sci. Hungar, 15:3–4 (1964), 445–447 | MR | Zbl

[16] Erd{ő}s P., Hajnal A., “On a property of families of sets”, Acta Math. Acad. Sci. Hungar, 12:1–2 (1961), 87–123 | MR | Zbl

[17] Erd{ő}s P., Lovász L., “Problems and results on 3-chromatic hypergraphs and some related questions”, Infinite and Finite Sets, v. 2, Colloq. Math. Soc. Jänos Bolyai, 10, ed. A. Hajnal, North-Holland, Amsterdam, 1975, 609–627 | MR

[18] Kostochka A. V., “Color-critical graphs and hypergraphs with few edges: A survey”, More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006, 175–197 | DOI | MR | Zbl

[19] Kostochka A. V., Kumbhat M., “Coloring uniform hypergraphs with few edges”, Random Struct. Algorithms, 35:3 (2009), 348–368 | DOI | MR | Zbl

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

[21] Pluhár A., “Greedy colorings for uniform hypergraphs”, Random Struct. Algorithms, 35:2 (2009), 216–221 | DOI | MR | Zbl

[22] Radhakrishnan J., Srinivasan A., “Improved bounds and algorithms for hypergraph 2-coloring”, Random Struct. Algorithms, 16:1 (2000), 4–32 | 3.0.CO;2-2 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[23] Shabanov D., “Coloring non-uniform hypergraphs without short cycles”, Graphs Combin., 30:5 (2014), 1249–1260 | DOI | MR | Zbl

[24] Shabanov D., “Around Erd{ő}s–Lovász problem on colorings of non-uniform hypergraphs”, Discrete Math., 338:11 (2015), 1976–1981 | DOI | MR | Zbl

[25] Shabanov D., “Equitable two-colorings of uniform hypergraphs”, European J. Combin., 43 (2015), 185–203 | DOI | MR | Zbl

[26] Szabó Z., “An application of Lovász local lemma — a new lower bound for the van der Waerden number”, Random Struct. Algorithms, 1:3 (1990), 343–360 | DOI | MR | Zbl