The regularity method for graphs with few 4-cycles

Abstract

We develop a sparse graph regularity method that applies to graphs with few 4-cycles, including new counting and removal lemmas for 5-cycles in such graphs. Some applications include: Every n-vertex graph with no 5-cycle can be made triangle-free by deleting o(n^(3/2)) edges. For r ⩾ 3, every n-vertex r-graph with girth greater than 5 has o(n^(3/2)) edges. Every subset of [n] without a nontrivial solution to the equation x₁ + x₂ + 2x₃ = x₄ + 3x₅ has size o(√n).

Files

Additional details