A Caltech Library Service

The regularity method for graphs with few 4-cycles

Conlon, David and Fox, Jacob and Sudakov, Benny and Zhao, Yufei (2020) The regularity method for graphs with few 4-cycles. . (Unpublished)

[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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:Conlon is supported 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-175573. 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-175573
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20200914-101307280
Persistent URL:
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:14 Sep 2020 17:20

Repository Staff Only: item control page