Hypergraph Ramsey numbers

Conlon, David¹ ; Fox, Jacob² ; Sudakov, Benny³

¹ St John’s College, Cambridge CB2 1TP, United Kingdom
² Department of Mathematics, Princeton University, Princeton, New Jersey 08544
³ Department of Mathematics, UCLA, Los Angeles, California 90095

Journal of the American Mathematical Society, Tome 23 (2010) no. 1, pp. 247-266

Résumé

The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-tuples of an $N$-element set contains a red set of size $s$ or a blue set of size $n$, where a set is called red (blue) if all $k$-tuples from this set are red (blue). In this paper we obtain new estimates for several basic hypergraph Ramsey problems. We give a new upper bound for $r_k(s,n)$ for $k \geq 3$ and $s$ fixed. In particular, we show that \[ r_3(s,n) \leq 2^{n^{s-2}\log n},\] which improves by a factor of $n^{s-2}/\textrm {polylog} n$ the exponent of the previous upper bound of Erdős and Rado from 1952. We also obtain a new lower bound for these numbers, showing that there is a constant $c>0$ such that \[ r_3(s,n) \geq 2^{c sn \log (\frac {n}{s}+1)}\] for all $4 \leq s \leq n$. For constant $s$, this gives the first superexponential lower bound for $r_3(s,n)$, answering an open question posed by Erdős and Hajnal in 1972. Next, we consider the $3$-color Ramsey number $r_3(n,n,n)$, which is the minimum $N$ such that every $3$-coloring of the triples of an $N$-element set contains a monochromatic set of size $n$. Improving another old result of Erdős and Hajnal, we show that \[ r_3(n,n,n) \geq 2^{n^{c \log n}}.\] Finally, we make some progress on related hypergraph Ramsey-type problems.

Détail

DOI : 10.1090/S0894-0347-09-00645-6

Bibliographie

[1] Ajtai, Miklã³S, Komlã³S, Jã¡Nos, Szemerã©Di, Endre A note on Ramsey numbers J. Combin. Theory Ser. A 1980 354 360

[2] Alon, Noga, Spencer, Joel H. The probabilistic method 2000

[3] Burkill, H., Mirsky, L. Monotonicity J. Math. Anal. Appl. 1973 391 410

[4] Chung, Fan, Graham, Ron Erdős on graphs 1998

[5] Erdã¶S, P. Some remarks on the theory of graphs Bull. Amer. Math. Soc. 1947 292 294

[6] Erdå‘S, P. On extremal problems of graphs and generalized graphs Israel J. Math. 1964 183 190

[7] Erdå‘S, P. On some extremal problems on 𝑟-graphs Discrete Math. 1971/72 1 6

[8] Erdå‘S, Paul Problems and results on graphs and hypergraphs: similarities and differences 1990 12 28

[9] Erdå‘S, P., Hajnal, A. On Ramsey like theorems. Problems and results 1972 123 140

[10] Erdå‘S, P., Hajnal, A. Ramsey-type theorems Discrete Appl. Math. 1989 37 52

[11] Erdå‘S, P., Hajnal, A., Rado, R. Partition relations for cardinal numbers Acta Math. Acad. Sci. Hungar. 1965 93 196

[12] Erdå‘S, P., Rado, R. Combinatorial theorems on classifications of subsets of a given set Proc. London Math. Soc. (3) 1952 417 439

[13] Erdã¶S, P., Szekeres, G. A combinatorial problem in geometry Compositio Math. 1935 463 470

[14] Faudree, R. J., Schelp, R. H. A survey of results on the size Ramsey number 2002 291 309

[15] Friedgut, Ehud, Kohayakawa, Yoshiharu, Rã¶Dl, Vojtä›Ch, Ruciå„Ski, Andrzej, Tetali, Prasad Ramsey games against a one-armed bandit Combin. Probab. Comput. 2003 515 545

[16] Graham, Ronald L., Rothschild, Bruce L., Spencer, Joel H. Ramsey theory 1980

[17] Kim, Jeong Han The Ramsey number 𝑅(3,𝑡) has order of magnitude 𝑡²/log𝑡 Random Structures Algorithms 1995 173 207

[18] Kostochka, A. V., Rã¶Dl, V. On Ramsey numbers of uniform hypergraphs with given maximum degree J. Combin. Theory Ser. A 2006 1555 1564

[19] Kã¶Vari, T., Sã³S, V. T., Turã¡N, P. On a problem of K. Zarankiewicz Colloq. Math. 1954 50 57

[20] Kurek, Andrzej, Ruciå„Ski, Andrzej Two variants of the size Ramsey number Discuss. Math. Graph Theory 2005 141 149

[21] Lovã¡Sz, Lã¡Szlã³ Combinatorial problems and exercises 2007 642

[22] Spencer, Joel Asymptotic lower bounds for Ramsey functions Discrete Math. 1977/78 69 76