Unavoidable patterns |
| |
Authors: | Jacob Fox Benny Sudakov |
| |
Institution: | a Department of Mathematics, Princeton University, Princeton, NJ 08544, USA b Department of Mathematics, UCLA, Los Angeles, CA 90095, USA |
| |
Abstract: | Let Fk 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 n(k,?) such that every 2-edge-coloring of the complete graph of order n?n(k,?) which has at least edges in each color contains a member of Fk. This conjecture was proved by Cutler and Montágh, who showed that n(k,?)<4k/?. We give a much simpler proof of this conjecture which in addition shows that n(k,?)<?−ck for some constant c. This bound is tight up to the constant factor in the exponent for all k and ?. We also discuss similar results for tournaments and hypergraphs. |
| |
Keywords: | Ramsey theory Ramsey-type problem for tournaments Dependent random choice |
本文献已被 ScienceDirect 等数据库收录! |
|