Edge-statistics on large graphs. (14th March 2020) - Alon, Noga; Hefetz, Dan; Krivelevich, Michael; Tyomkyn, Mykhaylo
Abstract: 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 ℓ a large graph G on n vertices can have. Clearly, this number is ( n k) for every n, k and { 0, ( k 2 )} . We conjecture that for every n, k and 0 ( k 2) this number is at most (1/e + o_k(1)) ( n k ) . If true, this would be tight for ℓ ∈ 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 ℓ we establish stronger bounds. In particular, we prove that for 'almost all' pairs ( k, ℓ ) only a polynomially small fraction of the k -subsets of V ( G ) have exactly ℓ edges, and prove an upper bound of (1/2 + o_k(1))( n k) for ℓ = 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.