Hypergraph Ramsey numbers

DOI10.1090/S0894-0347-09-00645-6zbMATH Open1287.05087arXiv0808.3760OpenAlexW2127163760MaRDI QIDQ3584347FDOQ3584347

Authors: David Conlon, Jacob Fox, Benny Sudakov

Publication date: 27 August 2010

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Abstract: 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 either 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}/ polylog n the exponent of the previous upper bound of Erdos and Rado from 1952. We also obtain a new lower bound for these numbers, showing that there are constants c_1,c_2>0 such that r_3(s,n) geq 2^{c_1 sn log (n/s)} for all 4 leq s leq c_2n. When s is a constant, it gives the first superexponential lower bound for r_3(s,n), answering an open question posed by Erdos 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 Erdos 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.

Full work available at URL: https://arxiv.org/abs/0808.3760

Recommendations

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Cites Work

Cited In (65)

This page was built for publication: Hypergraph Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584347)