Edge-statistics on large graphs. (14th March 2020)

• Record Type: Journal Article
• Authors: Alon, Noga; Hefetz, Dan; Krivelevich, Michael; Tyomkyn, Mykhaylo
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 2(2020)
• Page Start: 163
• Page End: 189
• Publication Date: 2020-03-14
• Subjects: 05C35, -- 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548319000294
• Languages: English
• ISSNs: 0963-5483

Abstract

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 $\left( {\matrix{n \cr k}}\right)$ for every n, k and $\ell \in \left\{ {0, \left( {\matrix{k \cr 2}} \right)}\right\}$ . We conjecture that for every n, k and $0 \lt \ell \lt \left( {\matrix{k \cr 2}}\right)$ this number is at most $ (1/e + {o_k}(1)) {\left( {\matrix{n \cr k}} \right)}$ . 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)){\left( {\matrix{n \cr k}}\right)}$ 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.