Large almost monochromatic subsets in hypergraphs

We show that for all t and epsilon > 0 there is a constant 
c=c(t,epsilon)>0 such that every t-coloring of the triples of an 
N-element set contains a subset S of
size c(log N)^{1/2} such that at least a 1-epsilon 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 Erdos and Hajnal from 1989 on
discrepancy in hypergraphs. For t > 3 colors, it is known that there is
a t-coloring of the triples of an N-element set whose largest
monochromatic subset has cardinality only on the order of log log N.
Thus, our result demonstrates that the maximum almost monochromatic
subset that a t-coloring of the triples must contain is much larger than
the corresponding monochromatic subset. This is in striking contrast
with graphs, where these two quantities have the same order of
magnitude. To prove our result, we obtain a new upper bound on the
t-color Ramsey numbers of complete multipartite 3-uniform hypergraphs,
which answers another open question of Erdos and Hajnal.

Joint work with D. Conlon and B. Sudakov.