A completion of the proof of the Edge-statistics Conjecture

Extremal combinatorics often deals with problems about maximizing some quantity related to substructures in large discrete structures. A basic question of this kind is to determine the maximum possible number of induced subgraphs of an $n$-vertex graph that are isomorphic to a fixed graph $H$. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number of vertices as $H$; this quantity is known as the inducibility of $H$. More generally, one can define the inducibility of a family of graphs in an analogous way.

Among all graphs with $k$ vertices, the only two graphs with inducibility equal to 1 are the empty graph and the complete graph. This raises the question of how large the inducibility of other graphs with $k$ vertices can be. A lower bound can be obtained as follows. Fix $k$, and consider a random graph with $n$ vertices where each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. Therefore, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: for each $l$ with $0<l<\binom{k}{2}$ the inducibility of the family of $k$-vertex graphs with exactly $l$ edges is at most $e^{-1}+o(1)$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $l$ is superlinearly bounded away from $0$ and $\binom{k}{2}$, for which the inducibility of the family of $l$-edge $k$-vertex graphs goes to zero, and also in the regime where $l$ is bounded away from $0$ and $\binom{k}{2}$ by a sufficiently large linear function. The article resolves the hardest cases where $l$ is linearly close to $0$ or close to $\binom{k}{2}$, and provides generalizations to hypergraphs.