Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 2021 | Submitted
Journal Article Open

The regularity method for graphs with few 4-cycles


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).

Additional Information

© 2021 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. Issue Online: 21 December 2021; Version of Record online: 30 September 2021; Manuscript revised: 10 May 2021; Manuscript received: 10 December 2020. We would like to thank Jacques Verstraëte and József Solymosi for helpful comments. Conlon is supported by NSF Award DMS-2054452 and in part by ERC Starting Grant 676632. Fox is supported by a Packard Fellowship and by NSF Award DMS-1855635. Sudakov is supported in part by SNSF grant 200021_196965. Zhao is supported by NSF Award DMS-1764176, the MIT Solomon Buchsbaum Fund, and a Sloan Research Fellowship.

Attached Files

Submitted - 2004.10180.pdf


Files (390.9 kB)
Name Size Download all
390.9 kB Preview Download

Additional details

August 20, 2023
October 20, 2023