Combinatorics Seminar
When: Sunday, January 4, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, UCLA
Title: Large almost monochromatic subsets in hypergraphs
Abstract:
We show that for all l and \epsilon>0 there is a constant
c=c(l,\epsilon)>0 such that every l-coloring of the triples of
an N-element set contains a subset S of size c\sqrt{\log N} such
that at least 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 l>=4 colors, it is known that there is an l-coloring of the
triples of an N-element set whose largest monochromatic subset has
cardinality only \Theta(\log \log N). Thus, our result
demonstrates
that the maximum almost monochromatic subset that an l-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 l-color Ramsey numbers
of
complete multipartite 3-uniform hypergraphs, which answers another
open
question of Erdos and Hajnal.
Joint work with D. Conlon and J. Fox.