Unavoidable patterns

2008/03/16 by Fox, Jacob, Sudakov, Benny · 2 citations
#05C20 #05C55 #05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0803.2375

Abstract

Let 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ás conjectured that for every ε>0 and positive integer k there is an n(k,ε) such that every 2-edge-coloring of the complete graph of order n ≥ n(k,ε) which has at least εn \choose 2 edges in each color contains a member of F_k. This conjecture was proved by Cutler and Montágh, who showed that n(k,ε)<4^k/ε. We give a much simpler proof of this conjecture which in addition shows that n(k,ε)

Cited by

• Color-avoiding directed paths in tournaments
• Relative discrepancy of hypergraphs

Related

• A note on unavoidable patterns in locally dense colourings
• Colored unavoidable patterns and balanceable graphs
• Unavoidable patterns in 2-colorings of the complete bipartite graph
• Ramsey-type problem for an almost monochromatic K₄
• The evolution of unavoidable bi-chromatic patterns and extremal cases of balanceability