Hypergraph Ramsey numbers

DOI10.1090/S0894-0347-09-00645-6MaRDI QIDQ3584347zbMATH OpenOpenAlexFDO

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)

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

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

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.

Recommendations

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)