Edge-statistics on large graphs

The inducibility of a graph $H$ measures the maximum number of induced copies of $H$ a large graph $G$ can have. Generalizing this notion, we study how many induced subgraphs of fixed order $k$ and size $\mathrm{\ell }$ a large graph $G$ on $n$ vertices can have. Clearly, this number is $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ for every $n$, $k$ and $\mathrm{\ell }\in \{0,\left(\genfrac{}{}{0px}{}{k}{2}\right)\}$. We conjecture that for every $n$, $k$ and $0<\mathrm{\ell }<\left(\genfrac{}{}{0px}{}{k}{2}\right)$ this number is at most $\left(1/e + o_k(1) \right) \binom{n}{k}$\mathrm{.}Iftrue,thiswouldbetightfor$\ell \in {1, k-1}$. In support of our Edge-statistics conjecture' we prove that the corresponding density is bounded away from $1$ by an absolute constant. Furthermore, for various ranges of the values of $\ell$ we establish stronger bounds. In particular, we prove that for almost all’ pairs $(k,\mathrm{\ell })$ only a polynomially small fraction of the $k$-subsets of $V(G)$ has exactly $\mathrm{\ell }$ edges, and prove an upper bound of $(1\mathrm{/}2+o_k(1))\left(\genfrac{}{}{0px}{}{n}{k}\right)$ for $\mathrm{\ell }=1$. Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun’s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov’s symmetrization, Sperner’s theorem and various counting techniques.