|
Organizers |
Hypergraph Ramsey problem
by
Benny Sudakov
UCLA
Coauthors: D. Conlon and J. Fox
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 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 several new estimates for basic hypergraph Ramsey problems.
First, we give a new upper bound for rk(s, n) for k ≥ 3 and s fixed, significantly improving the previous result of Erdös and Rado from 1952.
We also obtain the first superexponential lower bound for r3(s, n), answering an open question posed by Erdös and Hajnal in 1972.
Finally we show that for all r and e > 0, every r-coloring of the triples of an N-element set contains a subset S of size c√{logN} such that at least 1-e fraction of the triples of S have the same color. This result is tight up to the constant c and answers an open question of Erdös and Hajnal from 1989 on discrepancy in hypergraphs.
Date received: May 7, 2009
Copyright © 2009 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cayq-68.