A completion of the proof of the Edge-statistics Conjecture

Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. 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 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 the analogous way. Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join 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)$. So, 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: the inducibility of the family of $k$-vertex graphs with exactly $l$ edges where $0<l<\binom{k}{2}$ 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 sum of the inducibilities 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.