Counting sparse induced subgraphs in locally dense graphs

Abstract

An $n$-vertex graph $G$ is locally dense if every induced subgraph of size larger than $\zeta n$ has density at least $d>0$, for some parameters $\zeta ,d>0$. We show that the number of induced subgraphs of $G$ with $m$ vertices and maximum degree significantly smaller than $dm$ is roughly $\left(\genfrac{}{}{0ex}{}{\zeta n}{m}\right)$, for $m\ll \zeta n$ which is not too small. This generalises a result of Kohayakawa, Lee, Rödl, and Samotij on the number of independent sets in locally dense graphs. As an application, we slightly improve a result of Balogh, Chen, and Luo on the generalised Erdős-Rogers function for graphs with small extremal number.

4 pages; fixed minor issue in Lemma 2.1