Unavoidable patterns

Details Unavoidable patterns Unavoidable patterns

2008-03-16

arxiv.org/abs/0803.2375v2

Mathematics

Combinatorics

10 pages, corrected typos

Scientific paper

Let \mathcal{F}_k denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollob\'as conjectured that for every \epsilon>0 and positive integer k there is an n(k,\epsilon) such that every 2-edge-coloring of the complete graph of order n \geq n(k,\epsilon) which has at least \epsilon {n \choose 2} edges in each color contains a member of \mathcal{F}_k. This conjecture was proved by Cutler and Mont\'agh, who showed that n(k,\epsilon)<4^{k/\epsilon}. We give a much simpler proof of this conjecture which in addition shows that n(k,\epsilon)<\epsilon^{-ck} for some constant c. This bound is tight up to the constant factor in the exponent for all k and \epsilon. We also discuss similar results for tournaments and hypergraphs.

Affiliated with

Also associated with

No associations

Rating

Unavoidable patterns 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 Unavoidable patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unavoidable patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645746