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:
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