Edge-statistics on large graphs

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 91/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.