Large almost monochromatic subsets in hypergraphs

Details Large almost monochromatic subsets in hypergraphs Large almost monochromatic subsets in hypergraphs

2009-01-25

arxiv.org/abs/0901.3912v1

Mathematics

Combinatorics

Scientific paper

We show that for all $\ell$ and $\epsilon>0$ there is a constant $c=c(\ell,\epsilon)>0$ such that every $\ell$-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 Erd\H{o}s and Hajnal from 1989 on discrepancy in hypergraphs. For $\ell \geq 4$ colors, it is known that there is an $\ell$-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 $\ell$-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 $\ell$-color Ramsey numbers of complete multipartite 3-uniform hypergraphs, which answers another open question of Erd\H{o}s and Hajnal.

Affiliated with

Also associated with

No associations

Rating

Large almost monochromatic subsets in hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large almost monochromatic subsets in hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large almost monochromatic subsets in hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-504252