Linear dependence between hereditary quasirandomness conditions

Abstract

Answering a question of Simonovits and S\' os, Conlon, Fox, and Sudakov proved that for any nonempty graph $H$, and any $\epsilon >0$, there exists $\delta >0$ polynomial in $\epsilon$, such that if $G$ is an $n$-vertex graph with the property that every $U\subseteq V(G)$ contains $p^{e(H)}|U{|}^{v(H)}\pm \delta n^{v(H)}$ labeled copies of $H$, then $G$ is $(p,\epsilon )$-quasirandom in the sense that every subset $U\subseteq G$ contains $\frac{1}{2}p|U{|}^2\pm \epsilon n^2$ edges. They conjectured that $\delta$ may be taken to be linear in $\epsilon$ and proved this in the case that $H$ is a complete graph. We study a labelled version of this quasirandomness property proposed by Reiher and Schacht. Let $H$ be any nonempty graph on $r$ vertices $v_1,\dots ,v_r$, and $\epsilon >0$. We show that there exists $\delta =\delta (\epsilon )>0$ linear in $\epsilon$, such that if $G$ is an $n$-vertex graph with the property that every sequence of $r$ subsets $U_1,\dots ,U_r\subseteq V(G)$, the number of copies of $H$ with each $v_i$ in $U_i$ is $p^{e(H)}\prod |U_i|\pm \delta n^{v(H)}$, then $G$ is $(p,\epsilon )$-quasirandom.