SCIENCE@home

Hypergraph Ramsey numbers

D. Conlon,J. Fox,B. Sudakov

Published 2008 in Journal of the American Mathematical Society

ABSTRACT

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-28 of 28 references · Page 1 of 1

CITED BY

Showing 1-100 of 117 citing papers · Page 1 of 2

12
Next