CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959631

[img] PDF - Submitted Version
See Usage Policy.

210Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959631

Abstract

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
https://doi.org/10.1017/s0305004116001055DOIArticle
https://www.cambridge.org/core/journals/mathematical-proceedings-of-the-cambridge-philosophical-society/article/hereditary-quasirandomness-without-regularity/6CF793D412C0D7E4E6A34132698801C0PublisherArticle
https://arxiv.org/abs/1611.02099arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
David and Lucile Packard FoundationUNSPECIFIED
NSFDMS-1352121
Alfred P. Sloan FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021-149111
Issue or Number:3
Record Number:CaltechAUTHORS:20190812-162959631
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162959631
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
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:15 Aug 2019 17:04
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page