A Caltech Library Service

Edge-statistics on large graphs

Alon, Noga and Hefetz, Dan and Krivelevich, Michael and Tyomkyn, Mykhaylo (2020) Edge-statistics on large graphs. Combinatorics, Probability and Computing, 29 (2). pp. 163-189. ISSN 0963-5483. doi:10.1017/s0963548319000294.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© Cambridge University Press 2019. (Received 17 May 2018; revised 24 January 2019; first published online 14 November 2019) Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation. The research of Dan Hefetz is supported by ISF grant 822/18. Partially supported by USA-Israel BSF grants 2014361 and 2018267, and by ISF grant 1261/17. The research of Mykhaylo Tyomkyn is supported in part by ERC Starting Grant 633509. We thank the anonymous referee for carefully reading our paper and for providing helpful remarks.
Funding AgencyGrant Number
Israel Science Foundation281/17
Binational Science Foundation (USA-Israel)2018267
Simons FoundationUNSPECIFIED
Israel Science Foundation822/18
Binational Science Foundation (USA-Israel)2014361
Israel Science Foundation1261/17
European Research Council (ERC)633509
Issue or Number:2
Classification Code:2010 MSC Codes: Primary 05C35; Secondary 05D40
Record Number:CaltechAUTHORS:20201105-160425983
Persistent URL:
Official Citation:Alon, N., Hefetz, D., Krivelevich, M., & Tyomkyn, M. (2020). Edge-statistics on large graphs. Combinatorics, Probability and Computing, 29(2), 163-189. doi:10.1017/S0963548319000294
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106469
Deposited By: George Porter
Deposited On:06 Nov 2020 15:24
Last Modified:16 Nov 2021 18:54

Repository Staff Only: item control page