Unavoidable patterns
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 46958 (Why is no real title available?)
- scientific article; zbMATH DE number 3609704 (Why is no real title available?)
- scientific article; zbMATH DE number 2123255 (Why is no real title available?)
- scientific article; zbMATH DE number 3221981 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- A few remarks on Ramsey--Turán-type problems
- A new upper bound for diagonal Ramsey numbers
- Density theorems for bipartite graphs and related Ramsey-type results
- Graphs with many r -cliques have large complete r -partite subgraphs
- On graphs with small Ramsey numbers
- Some remarks on the theory of graphs
- Unavoidable subgraphs of colored graphs
Cited in
(24)- Unavoidable tournaments
- Recent developments on unavoidable patterns in 2-colorings of the complete graph
- Two Ramsey problems in blowups of graphs
- Non-monochromatic triangles in a 2-edge-coloured graph
- Large unavoidable subtournaments
- Minimum degree and the graph removal lemma
- Unavoidable patterns in locally balanced colourings
- Unavoidable subgraphs of colored graphs
- Turán‐ and Ramsey‐type results for unavoidable subgraphs
- Anticoncentration for subgraph statistics
- On 2-colored graphs and partitions of boxes
- The probability of intransitivity in dice and close elections
- Unavoidable order-size pairs in hypergraphs -- positive forcing density
- Finding unavoidable colorful patterns in multicolored graphs
- Note on Gy. Elekes's conjectures concerning unavoidable patterns in proper colorings
- Ramsey numbers upon vertex deletion
- Unavoidable chromatic patterns in 2‐colorings of the complete graph
- Dependent random choice
- Large unavoidable subtournaments
- Turán theorems for unavoidable patterns
- The balancing number and generalized balancing number of some graph classes
- Unbalanced spanning subgraphs in edge labeled complete graphs
- The removal lemma for tournaments
- scientific article; zbMATH DE number 5704250 (Why is no real title available?)
This page was built for publication: Unavoidable patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q958758)
