Edge-statistics on large graphs

Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn

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 $\ell$ a large graph $G$ on $n$ vertices can have. Clearly, this number is $\binom{n}{k}$ for every $n, k$ and $\ell \in \{0, \binom{k}{2}\}$. We conjecture that for every $n, k$ and $0 < \ell < \binom{k}{2}$ this number is at most $(1/e + o_k(1)) \binom{n}{k}$. If true, this would be tight for $\ell \in \{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 $\ell$ we establish stronger bounds. In particular, we prove that for ‘almost all’ pairs $(k, \ell)$ only a polynomially small fraction of the $k$-subsets of $V(G)$ have exactly $\ell$ edges, and prove an upper bound of $(1/2 + o_k(1))\binom{n}{k}$ for $\ell = 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.

Introduction

In extremal graph theory, the concept of inducibility asks: given a small graph $H$, what is the maximum number of induced copies of $H$ we can find in a much larger graph $G$? This paper generalizes that question to edge-inducibility: given $k$ and $\ell$, what is the maximum density of $k$-vertex induced subgraphs that contain exactly $\ell$ edges?

While it is trivial to maximize density for $\ell=0$ (empty graph) or $\ell=\binom{k}{2}$ (complete graph), intermediate values of $\ell$ present a significant challenge. The authors propose the Edge-statistics Conjecture, suggesting that for any $0 < \ell < \binom{k}{2}$, the maximum density is at most $1/e + o_k(1)$.

Methods

The study employs a diverse toolkit of probabilistic and combinatorial methods:

  • Anti-concentration Inequalities: Fourth-moment estimates are used to show that the number of edges in a $k$-subset cannot be overly concentrated on a single value.
  • Zykov’s Symmetrization: This tool transforms graphs into structured versions (like complete multipartite graphs) to facilitate counting.
  • Brun’s Sieve: Applied in the "fixed $\ell$" regime to demonstrate that edge counts in sparse subgraphs follow a Poisson distribution.
  • Sperner’s Theorem and Littlewood-Offord Theory: Used to handle the quadratic regime where $\ell \approx k^2$, treating edge counts as sums of independent indicators.

Key Insights

  • The $1/e$ Threshold: The conjectured $1/e$ limit (approx. 36.7%) arises from Poisson distributions in semi-random constructions where the mean number of edges is 1.
  • Invariance under Complements: Edge-inducibility is symmetric: $ind(k, \ell) = ind(k, \binom{k}{2} - \ell)$.
  • Global-Local Equilibrium: A maximizing graph must satisfy a property where the local probability of a $k$-set containing a specific vertex having $\ell$ edges matches the global density.
  • Structure vs. Randomness: High concentration is only possible when $\ell$ is small (linear in $k$); for most values, the density is polynomially small ($O(k^{-0.1})$).

Key Results

The paper establishes several upper bounds for the edge-inducibility $ind(k, \ell)$ across different regimes of $\ell$, as summarized in the following table:

Summary of upper bounds on edge-inducibility for various ranges of $\ell$.

As shown above, the bounds vary significantly by regime:

  • General Bound: For any $k$ and $0 < \ell < \binom{k}{2}$, the density is bounded by $1 - \epsilon$.
  • Quadratic Regime: When $\ell$ is proportional to $k^2$, the density drops to $O(k^{-0.1})$.
  • Fixed and Linear Regimes: For $\ell=1$, the bound is $1/2$. For constant $\ell$, it is $3/4$.

Conclusion

While the proven bounds are steps toward the Edge-statistics Conjecture, a gap remains between the current results (e.g., $1/2$ or $3/4$) and the conjectured $1/e$. However, recent work mentioned in the paper's addendum has begun to close this gap for various ranges of $\ell$, validating the authors' core intuition.

Summary updated

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.
BibTeX
@article{alon2020edge,
  author = {Noga Alon and Dan Hefetz and Michael Krivelevich and Mykhaylo Tyomkyn},
  title = {{Edge-statistics on large graphs}},
  journal = {Comb. Probab. Comput.},
  year = {2020},
  doi = {10.1017/s0963548319000294},
}
Figure