Hypergraph Ramsey numbers

By David Conlon, Jacob Fox, Benny Sudakov. 2008

126 citations recorded by the source corpus.

The Ramsey number rk(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 rk(s, n) for k ≥ 3 and s fixed. In particular, we show that r3(s, n) ≤ 2 s−2 log , which improves by a factor of ns−2/polylogn 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 r3(s, n) ≥ 2 sn log( n s +1) for all 4 ≤ s ≤ n. For constant s, it gives the first superexponential lower bound for r3(s, n), answering an open question posed by Erdős and Hajnal in 1972. Next, we consider the 3-color Ramsey number r3(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 r3(n, n, n) ≥ 2 c log n . Finally, we make some progress on related hypergraph Ramsey-type problems.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/fda70d369e3f55cd0f7f56e7b797b86b25896385

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Erdős–Szekeres‐type theorems for monotone paths and convex bodies (2011, methodology): “[10] used online Ramsey numbers to give an upper bound for the Ramsey number of a complete k-uniform hypergraph with n vertices.”