A Caltech Library Service

Hereditary quasirandomness without regularity

Conlon, David and Fox, Jacob and Sudakov, Benny (2018) Hereditary quasirandomness without regularity. Mathematical Proceedings of the Cambridge Philosophical Society, 164 (3). pp. 385-399. ISSN 0305-0041. doi:10.1017/s0305004116001055.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A result of Simonovits and Sós states that for any fixed graph H and any ϵ > 0 there exists δ > 0 such that if G is an n-vertex graph with the property that every S ⊆ V(G) contains p^(e(H))|S|^(v(H)) ± δn^(v(H)) labelled copies of H, then G is quasirandom in the sense that every S ⊆ V(G) contains ½p|S|^2 ± ϵn^2 edges. The original proof of this result makes heavy use of the regularity lemma, resulting in a bound on δ^(−1) which is a tower of twos of height polynomial in ϵ^(−1). We give an alternative proof of this theorem which avoids the regularity lemma and shows that δ may be taken to be linear in ϵ when H is a clique and polynomial in ϵ for general H. This answers a problem raised by Simonovits and Sós.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
Additional Information:© Cambridge Philosophical Society 2017. First published online 26 January 2017. Conlon supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. Fox supported by a Packard Fellowship, by NSF Career Award DMS-1352121 and by an Alfred P. Sloan Fellowship. Sudakov supported by SNSF grant 200021-149111.
Funding AgencyGrant Number
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
Alfred P. Sloan FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021-149111
Issue or Number:3
Record Number:CaltechAUTHORS:20190812-162959631
Persistent URL:
Official Citation:CONLON, DAVID, JACOB FOX, and BENNY SUDAKOV. “Hereditary Quasirandomness without Regularity.” Mathematical Proceedings of the Cambridge Philosophical Society 164, no. 3 (2018): 385–99. doi:10.1017/S0305004116001055.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97830
Deposited By: Melissa Ray
Deposited On:15 Aug 2019 17:04
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page