The regularity method for graphs with few 4-cycles

2021 
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).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    45
    References
    0
    Citations
    NaN
    KQI
    []