A Caltech Library Service

The regularity method for graphs with few 4-cycles

Conlon, David and Fox, Jacob and Sudakov, Benny and Zhao, Yufei (2021) The regularity method for graphs with few 4-cycles. Journal of the London Mathematical Society . ISSN 0024-6107. doi:10.1112/jlms.12500. (In Press)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:© 2021 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. 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.
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021_196965
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Classification Code:2020 Mathematics Subject Classification: 05C35, 05D40, 11B99, 11P99 (primary).
Record Number:CaltechAUTHORS:20200914-101307280
Persistent URL:
Official Citation:Conlon, D., Fox, J., Sudakov, B. and Zhao, Y. (2021), The regularity method for graphs with few 4-cycles. J. London Math. Soc.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105369
Deposited By: Tony Diaz
Deposited On:14 Sep 2020 17:20
Last Modified:05 Oct 2021 18:30

Repository Staff Only: item control page