Geodesic
On the Erdős–Hajnal problem in the case of $3$-graphs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 168-176 
D. D. Cherkashin. On the Erdős–Hajnal problem in the case of $3$-graphs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part XI, Tome 488 (2019), pp. 168-176. http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a7/
@article{ZNSL_2019_488_a7,
     author = {D. D. Cherkashin},
     title = {On the {Erd\H{o}s{\textendash}Hajnal} problem in the case of $3$-graphs},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {168--176},
     year = {2019},
     volume = {488},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a7/}
}
TY  - JOUR
AU  - D. D. Cherkashin
TI  - On the Erdős–Hajnal problem in the case of $3$-graphs
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2019
SP  - 168
EP  - 176
VL  - 488
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a7/
LA  - en
ID  - ZNSL_2019_488_a7
ER  - 
%0 Journal Article
%A D. D. Cherkashin
%T On the Erdős–Hajnal problem in the case of $3$-graphs
%J Zapiski Nauchnykh Seminarov POMI
%D 2019
%P 168-176
%V 488
%U http://geodesic.mathdoc.fr/item/ZNSL_2019_488_a7/
%G en
%F ZNSL_2019_488_a7

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable. For the broad history of the problem see [10]. It is known [4] that for a fixed $n$ the sequence $$ \frac{m(n,r)}{r^n} $$ has a limit. The only trivial case is $n=2$ in which $m(2,r) = \binom{r+1}{2}$. In this note we focus on the case $n=3$. First, we compare the existing methods in this case and then improve the lower bound.

[1] I. A. Akolzin, “On $3$-homogeneous hypergraphs colorings in $3$ colors”, Itogi Nauki i Tekhniki. Seriya Sovrem. Matem. i ee Prilozhen. Tenaticheskie Obzory, 150, 2018, 26–39 | MR

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

[3] N. Alon, “Hypergraphs with high chromatic number”, Graphs and Combinatorics, 1:1 (1985), 387–389 | DOI | MR | Zbl

[4] D. Cherkashin, F. Petrov, Regular behavior of the maximal hypergraph chromatic number, 2018, arXiv: 1808.01482

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

[6] P. Erdős, “Some old and new problems in various branches of combinatories”, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXIII, Utilitas Mathematica, Winnipeg, 1979, 19–37 | MR

[7] P. Erdős, A. Hajnal, “On a property of families of sets”, Acta Mathematica Hungarica, 12:1–2 (1961), 87–123 | MR | Zbl

[8] N. Pippenger, M. Ch. Golumbic, “The inducibility of graphs”, J. Combinatorial Theory, Series B, 19:3 (1975), 189–203 | DOI | MR | Zbl

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

[10] A. M. Raigorodskii, D. A. Shabanov, “The Erdős–Hajnal problem of hypergraph colouring, its generalizations, and related problems”, Russian Mathematical Surveys, 66:5 (2011), 933–1002 | DOI | MR | Zbl

[11] A. Sidorenko, “What we know and what we do not know about Turán numbers”, Graphs and Combinatorics, 11:2 (1995), 179–199 | DOI | MR | Zbl