A large $\gamma$-self-regular set whose density lies between $\eta$ and $1-\eta$ forces at least $c\mathrm{\mid }W{\mathrm{\mid }}^{\mathrm{\mid }V(H)\mathrm{\mid }}$ induced copies of $H$

Given: A graph $H$ with $h$ vertices, a real $0<\eta <1\mathrm{/}2$, a graph $G$, a set $W\subseteq V(G)$ with $\mathrm{\mid }W\mathrm{\mid }\ge N(H,\eta )$, and a real $0<\gamma \le \gamma (H,\eta )$ such that $(W,W)$ is $\gamma$-regular and $\eta \le d_G(W,W)\le 1-\eta$.

If $0<\eta <1\mathrm{/}2$, the induced counting lemma supplies $\gamma (H,\eta ),c(H,\eta )>0$ and $N(H,\eta )$; it applies to $h$ sets $W_i$ of size at least $N(H,\eta )$, repetitions allowed, when every relevant pair is $\gamma (H,\eta )$-regular and the edge- and nonedge-density bounds hold, and then yields at least $c(H,\eta ){\prod }_i\mathrm{\mid }{W}_i\mathrm{\mid }$ induced embeddings of $H$ (Induced counting lemma: regular edge and nonedge pairs force many induced copies).

If $0<\gamma \le \gamma (H,\eta )$ and $(W,W)$ is $\gamma$-regular, then it is also $\gamma (H,\eta )$-regular: any $A,B\subseteq W$ with $\mathrm{\mid }A\mathrm{\mid }\ge \gamma (H,\eta )\mathrm{\mid }W\mathrm{\mid }$ and $\mathrm{\mid }B\mathrm{\mid }\ge \gamma (H,\eta )\mathrm{\mid }W\mathrm{\mid }$ also satisfy the $\gamma$-threshold, so the defining density deviation is at most $\gamma \le \gamma (H,\eta )$ ($ϵ$-regular pairs and self-regular vertex sets).

The induced-copy number counts induced embeddings of $H$ (The induced-embedding count ${\mathrm{ind}}_H(G)$, Induced embeddings and induced copies of a graph).