Edge-statistics on large graphs

Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn

TL;DR

This paper explores "edge-statistics" in large graphs, investigating the maximum possible density of $k$-vertex induced subgraphs that contain exactly $\ell$ edges. The authors propose the "Edge-statistics Conjecture"—suggesting this density is at most $1/e + o_k(1)$—and provide several foundational proofs that bound these densities away from 1 across various ranges of $\ell$.

What Problem Does This Paper Address?

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. Instead of looking for a specific graph $H$, the authors look for any induced subgraph on $k$ vertices that has exactly $\ell$ edges. They define this as the edge-inducibility of $k$ and $\ell$.

The challenge lies in the fact that while it's easy to make a graph where every $k$-vertex subgraph has 0 edges (an empty graph) or $\binom{k}{2}$ edges (a complete graph), it is much harder to "force" a specific intermediate number of edges $\ell$ to appear frequently. The authors seek to determine the fundamental limits of how concentrated the edge distribution of induced subgraphs can be.

Methods

The authors employ a sophisticated mix of probabilistic and combinatorial techniques:

  • Anti-concentration Inequalities: To prove that the edge density cannot be too high, they use fourth-moment estimates to show that the random variable representing the number of edges in a $k$-subset cannot be overly concentrated on a single value.
  • Zykov’s Symmetrization: A standard tool in extremal graph theory used to transform a graph into a more structured version (like a complete multipartite graph) without decreasing the count of certain subgraphs.
  • Brun’s Sieve: Used specifically for the "fixed $\ell$" regime to show that edge counts in sparse subgraphs behave like a Poisson distribution.
  • Sperner’s Theorem and Littlewood-Offord Theory: These combinatorial tools are used to handle cases where $\ell$ is large (quadratic in $k$), treating the edge count as a sum of (mostly) independent indicators.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and logical derivations rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • The $1/e$ Threshold: The authors conjecture that for any $0 < \ell < \binom{k}{2}$, the maximum density is roughly $1/e$ (approx. 36.7%). This specific constant arises because, in certain random or semi-random constructions, the number of edges follows a Poisson distribution with mean 1, and the probability of a Poisson(1) variable equaling 1 is $1/e$.
  • Invariance under Complements: The edge-inducibility of $(k, \ell)$ is the same as $(k, \binom{k}{2} - \ell)$. This symmetry allows the authors to focus primarily on the "lower half" of possible edge counts.
  • Global-Local Criterion: Lemma 2.1 establishes that if a graph $G$ maximizes the density of $\ell$-edge subgraphs, then for every vertex $v$, the probability that a random $k$-set containing $v$ has $\ell$ edges must be roughly equal to the overall density. This "equilibrium" property is a powerful starting point for their proofs.
  • Structure vs. Randomness: The paper shows that for "almost all" values of $\ell$, the density is actually polynomially small ($O(k^{-0.1})$), meaning that high concentration of edge counts is only possible when $\ell$ is relatively small (linear in $k$).

Key Results

  • General Bound (Theorem 1.3): For any $k$ and $0 < \ell < \binom{k}{2}$, the edge-inducibility is bounded away from 1 by an absolute constant ($1 - \epsilon$).
  • The Quadratic Regime (Theorem 1.5): If $\ell$ is proportional to $k^2$ (and not too close to the maximum), the density is very small: $O(k^{-0.1})$.
  • Fixed Edge Counts (Theorem 1.6):
    • For any fixed $\ell$, the density is at most $3/4 + o_k(1)$.
  • For the specific case of $\ell = 1$, the density is at most $1/2 + o_k(1)$.
  • Linear Regime (Proposition 1.4): If $\ell$ is linear in $k$ (e.g., $\ell = Ck$), the density is at most $1/2 + \epsilon$.

Limitations and Future Work

  • The Gap to $1/e$: While the authors conjecture $1/e$ is the true limit, their proven upper bounds (like $3/4$ or $1/2$) are still significantly higher than $1/e$ for many cases.
  • Explicit Constants: The $\epsilon$ in the general bound ($1-\epsilon$) is not explicitly calculated in the main proof, though the authors suggest $\epsilon = 1/10$ might be achievable with their methods.
  • Addendum Note: The paper includes an addendum noting that since its original submission, other researchers (Kwan, Sudakov, Tran, Fox, and Sauermann) have successfully proved the Edge-statistics Conjecture ($1/e$ bound) for various ranges of $\ell$, essentially validating the authors' primary 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},
}

Loading related content...

Figure