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.