Hereditary quasirandomness without regularity

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.

Files

Additional details