Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2018 | Submitted
Journal Article Open

Hereditary quasirandomness without regularity


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.

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.

Attached Files

Submitted - 1611.02099.pdf


Files (215.5 kB)
Name Size Download all
215.5 kB Preview Download

Additional details

August 19, 2023
October 18, 2023