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