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 (k2)−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<(k2) 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 (k2), 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 (k2) by a sufficiently large linear function. The article resolves the hardest cases where l is linearly close to 0 or close to (k2), and provides generalizations to hypergraphs.