Hereditary quasirandomness without regularity

Abstract

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

15 pages