A Caltech Library Service

Bounds for graph regularity and removal lemmas

Conlon, David and Fox, Jacob (2012) Bounds for graph regularity and removal lemmas. Geometric and Functional Analysis, 22 (5). pp. 1191-1256. ISSN 1016-443X. doi:10.1007/s00039-012-0171-x.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck^(2)/log^* k pairs of parts which are not ϵ-regular, where c, ϵ > 0 are absolute constants. This bound is tight up to the constant c and addresses a question of Gowers on the number of irregular pairs in Szemerédi’s regularity lemma. In order to gain some control over irregular pairs, another regularity lemma, known as the strong regularity lemma, was developed by Alon, Fischer, Krivelevich, and Szegedy. For this lemma, we prove a lower bound of wowzer-type, which is one level higher in the Ackermann hierarchy than the tower function, on the number of parts in the strong regularity lemma, essentially matching the upper bound. On the other hand, for the induced graph removal lemma, the standard application of the strong regularity lemma, we find a different proof which yields a tower-type bound. We also discuss bounds on several related regularity lemmas, including the weak regularity lemma of Frieze and Kannan and the recently established regular approximation theorem. In particular, we show that a weak partition with approximation parameter ϵ may require as many as 2^Ω(ϵ^(−2)) parts. This is tight up to the implied constant and solves a problem studied by Lovász and Szegedy.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:© 2012 Springer Basel AG. Received 23 July 2011; revised 03 May 2012; accepted 07 May 2012; first online 25 August 2012. David Conlon’s research was supported by a Royal Society University Research Fellowship and Jacob Fox’s research was supported by a Simons Fellowship and NSF grant DMS-1069197. We would like to thank Noga Alon for helpful comments. We also thank the anonymous referee for carefully reading the article and making several useful remarks.
Funding AgencyGrant Number
Simons FoundationUNSPECIFIED
Subject Keywords:Bipartite Graph; Random Graph; Edge Density; Graph Regularity; Regularity Lemma
Issue or Number:5
Record Number:CaltechAUTHORS:20190812-162959355
Persistent URL:
Official Citation:Conlon, D. & Fox, J. Geom. Funct. Anal. (2012) 22: 1191.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97827
Deposited By: Melissa Ray
Deposited On:15 Aug 2019 17:47
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page