Unavoidable patterns
| dc.creator | Fox, Jacob | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-03-16 | |
| dc.date | 2008-04-06 | |
| dc.date.accessioned | 2026-07-07T09:30:16Z | |
| dc.date.available | 2026-07-07T09:30:16Z | |
| dc.description | 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á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 \geq n(k,ε) which has at least ε{n \choose 2} edges in each color contains a member of \mathcal{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,ε)<ε^{-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. | |
| dc.description | 10 pages, corrected typos | |
| dc.identifier | https://arxiv.org/abs/0803.2375 | |
| dc.identifier | http://arxiv.org/abs/0803.2375 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158070 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C55; 05C20; 05D10 | |
| dc.title | Unavoidable patterns | |
| dc.type | text |