Source-linked AI summary
An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
Christian Borgs, Jennifer T. Chayes, Henry Cohn, Yufei Zhao
TL;DR
Sparse graph limit theory has lacked a broadly applicable framework for graphs with unbounded average degrees and power-law degree distributions. This paper develops an L^p graphon theory with weaker assumptions than the Bollobás–Riordan approach, characterizes convergence, and constructs sparse random graph models. It establishes compactness and convergence results while identifying scope boundaries for the L^1 case and graph-to-graph regularity transfer.
Problem
Existing graph-limit theories cover dense graphs, bounded-average-degree graphs, or sparse graphs without dense spots, leaving many power-law networks outside their scope.
Method
The paper develops L^p graphons for p > 1, uses L^p upper regularity and cut-metric convergence, and constructs sparse W-random graph models.
Results
Every L^p upper regular graph sequence with p > 1 has a convergent subsequence, and sparse W-random graphs converge to W with probability 1.
Takeaways & Limitations
The L^p framework extends graph limits to sparse graphs with power-law behavior and unbounded average degrees.
Takeaways & Limitations
For p = 1, compactness fails without additional hypotheses such as uniform integrability, and graph upper regularity does not generally imply graphon upper regularity in the converse direction.
Abstract
from arXiv · showhide
We introduce and develop a theory of limits for sequences of sparse graphs based on $L^p$ graphons, which generalizes both the existing $L^\infty$ theory of dense graph limits and its extension by Bollobás and Riordan to sparse graphs without dense spots. In doing so, we replace the no dense spots hypothesis with weaker assumptions, which allow us to analyze graphs with power law degree distributions. This gives the first broadly applicable limit theory for sparse graphs with unbounded average degrees. In this paper, we lay the foundations of the $L^p$ theory of graphons, characterize convergence, and develop corresponding random graph models, while we prove the equivalence of several alternative metrics in a companion paper.
1. Introduction
The paper addresses the lack of a broadly applicable limit theory for sparse graphs with unbounded average degrees and power-law structure. It develops an L^p graphon framework that generalizes earlier dense and sparse theories, characterizes convergence, and supplies corresponding random graph models.
- Sparse graph limits must cover networks beyond bounded-average-degree graphs and dense graphs, which capture only O(n) and Ω(n^2) edges, respectively.
- The Bollobás–Riordan theory extends graphons to sparse graphs but assumes no especially dense spots, excluding many power-law network models.
- The paper develops L^p graphons for all p > 1, extending dense graph limits and Bollobás–Riordan theory as the special case p = ∞.
- The framework provides flexibility for power laws and unbounded sparse-graph densities, which bounded graphons cannot represent simultaneously.
- The authors establish an L^p weak Szemerédi regularity lemma and characterize convergence through L^p upper regularity and the cut metric.
- Every L^p upper regular graph sequence with p > 1 has a convergent subsequence, while sparse W-random graphs converge almost surely to their L^1 graphon W.
2. Definitions and results
This section defines weighted graphs, graphons, normalization, and L^p upper regularity for sparse-graph analysis. It then connects these objects through associated graphons, stepping operators, and the compactness-oriented regularity framework.
- Weighted graphs: Weighted graphs assign positive vertex weights and real edge weights, with simple unweighted graphs as a special case.
- Upper L^p regularity: The paper imposes partition-based L^p bounds rather than a uniform graph L^p norm because the latter would force simple graphs to be dense.
- Upper L^p regularity: Upper L^p regularity bounds partition-averaged edge densities after normalization while requiring sufficiently large parts and no dominant vertex weight.
- Graphons: A graphon is a symmetric integrable function, and an L^p graphon additionally has finite ∥W∥p.
- Associated graphons: The associated graphon partitions [0,1] into intervals proportional to vertex weights and assigns each rectangle the corresponding edge weight.
- Normalization: For sparse graphs, normalizing by ∥G∥1 produces associated graphons that remain informative instead of converging trivially to zero.
- Stepping operator: The stepping operator averages a graphon over partition cells and is contractive for both the cut norm and all L^p norms.
- Graphons and regularity: Graph upper L^p regularity implies the corresponding normalized graphon is upper L^p regular under the stated vertex-weight condition, but the converse can fail because graphon partitions need not respect vertex atoms.
2.4. Cut metric.
The cut metric compares graphons through the cut norm while allowing measure-preserving relabelings. For sparse graphs with differing densities, the paper applies the metric to normalized associated graphons.
- Graphon cut metric: The cut metric identifies graphons up to measure-preserving bijections of [0,1].
- Graphon cut metric: The cut norm is defined by maximizing the absolute integral of a graphon over measurable sets S and T.
- Graphon cut metric: The cut metric is equivalent to the L∞→L1 operator norm formulation.
- Graph cut distance: For weighted graphs on the same vertex set, the cut distance can be expressed using vertex subsets because the associated graphons share the same partition.
- Graph cut distance: Graphs with different vertex sets are compared through graphon-based definitions rather than the same-vertex-set cut distance.
- Normalized cut metric: Graphs with different densities are compared by applying the cut metric to their normalized associated graphons.
2.5. Lp upper regular sequences.
Lp upper regularity characterizes when normalized sparse graph sequences admit graphon limits and supplies compactness for Lp graphons. For p > 1, the theory gives subsequential convergence, while convergence to an Lp graphon implies upper regularity; p = 1 requires additional hypotheses.
- Definition: An Lp upper regular sequence is asymptotically (C + o(1), o(1))-upper Lp regular for every p > 1.The definition requires an n0(η) after which each graph is (C + η, η)-upper Lp regular.
- Existence of limits: Every C-upper Lp regular weighted-graph sequence has a subsequence whose normalized graphons converge in cut metric to an Lp graphon W with ∥W∥p ≤ C.An analogous limit theorem holds for Lp upper regular graphon sequences.
- Characterization: Convergence to an Lp graphon implies ∥W∥p-upper Lp regularity, with the weighted-graph version obtained by normalizing associated graphons.For weighted graphs, the result also applies under no dominant nodes.
- Necessity: Without Lp upper regularity, normalized graph sequences may fail both to have a Cauchy subsequence and to converge even when Cauchy.The paper gives examples with pairwise normalized cut distance at least 1/2 and with Cauchy but nonconvergent sequences.
- Compactness: For 1 < p ≤ ∞, the Lp ball of graphons is compact under cut metric after identifying points at distance zero.This extends compactness of [0,1]-valued graphons to Lp graphons.
- Compactness: The analogous L1 compactness claim is false without uniform integrability or other additional hypotheses.The L1 graphon ball is neither totally bounded nor complete under cut metric, while an L1 version holds under uniform integrability.
2.7. Sparse W-random graph models.
Sparse W-random graph models are built by sampling a graphon into a weighted graph and then independently sparsifying its edges. Under stated scaling conditions, these models converge to the generating graphon in normalized cut metric and support quasirandom approximation.
- Construction: Given a graphon W, H(n, W) samples i.i.d. uniform points and assigns edge ij the weight W(xi, xj).The sampled weighted graph can also be viewed as a graphon using intervals of length 1/n ordered by the sample points.
- Construction: For nonnegative edge weights βij, G(H, ρ) independently includes ij with probability min{ρβij, 1}; negative weights yield ±1 edge weights.The sparse W-random graph is defined by G(n, W, ρ) := G(H(n, W), ρ).
- Convergence: The convergence theorem uses the same i.i.d. sample sequence across n and distinguishes ordered metrics d1 and d□ from permutation-invariant metrics δ1 and δ□.The ordered vertices follow the ordering of the sampled points, which is not determined by the graphs alone.
- Conditions: If ρn → 0 and nρn → ∞, the sparse random graphs converge under the theorem’s normalized scaling; the second condition makes expected average degree diverge.The sparsity condition is needed to see the unbounded part of W, and diverging nρn is necessary by the cited results.
- Quasirandomness: Sparse simple graph sequences converging to an Lp graphon are close in cut metric to corresponding W-random graphs.This gives a quasirandom interpretation for sparse graphs approximating W.
- Densification: Densifying approximates an Lp upper regular graph by an Lp graphon in cut distance, transferring between sparse large edge weights and dense small Lp-bounded weights.The paper states this as a transference theorem and establishes it via a weak regularity lemma with boundedly many partition parts.
- Regularity: The weak regularity lemma extends prior L∞ results to Lp upper regular graphs using an L2 energy increment argument and truncation when 1 < p < 2.The truncation issue arises from limited control of maximum L2 energy; analogous p = 1 arguments require tail control.
2.9. Counting lemma for Lp graphons.
In sparse graphs, cut-metric convergence does not generally control homomorphism densities, so counting lemmas require stronger Lp conditions. For Lp graphons, the paper establishes the sharp threshold p>Δ, where Δ is the pattern's maximum degree.
- Sparse counting failure: In sparse graphs, normalized cut-distance convergence need not imply convergence of homomorphism densities, unlike in dense graph limits.The paper identifies this failure as an unavoidable consequence of sparsity.
- Sparse counting failure: When ρ_n=o(n^-1/2), deleting all triangle edges removes only an o(1) edge fraction but produces a graph with very different normalized triangle density.The two graphs remain close in normalized cut distance despite this density difference.
- Lp threshold: For an Lp graphon W and pattern F of maximum degree Δ, t(F,W) can be infinite when p<Δ, whereas W∈L^Δ guarantees finite, well-defined density.The bound is controlled by the L^Δ norm and the number of edges of F.
- Lp threshold: A counting lemma holds for Lp graphons when p>Δ: small cut distance and bounded Lp norms force |t(F,U)−t(F,W)| to be small.The resulting bound tends to zero with ε and converges to the L∞ theorem's bound as p→∞.
- Lp threshold: Uniform Lp bounds plus cut-metric convergence imply convergence of F-densities for every simple graph whose maximum degree is less than p.Lp upper regularity alone does not suffice for this conclusion.
- Sharpness: No analogous counting lemma holds for p≤Δ, even with L1 distance: graphons can converge to 1 in L1 while their F-densities converge to a different value.The counterexample maintains uniformly bounded Lp norms.
3. Lp graphons
The paper develops compactness and convergence foundations for Lp graphons using weak regularity, step-function approximations, and martingale convergence. These arguments show that bounded Lp balls are compact in cut metric for p>1.
- Lp graphon limits: An Lp graphon is a symmetric integrable function on [0,1]^2 with finite Lp norm, and the section proves a limit theorem for such graphons.The proof establishes the Lp graphon sequence-to-limit arrow.
- Weak regularity: Weak regularity approximates Lp graphons by step functions through refinements of partitions, using the L2 energy argument for p≥2 and truncation for 1<p<2.The method extends the weak regularity lemma across the full range p>1.
- Weak regularity: The construction can enforce equipartitions while controlling cut-norm error through refinement, contractivity of the stepping operator, and Hölder's inequality.The equitizing lemma produces exactly k|P| parts and bounds the resulting approximation error.
- Compactness proof: The compactness proof takes limits of fixed-part step approximations, aligns their partitions by measure-preserving bijections, and organizes the limits into a martingale.The martingale convergence theorem then supplies the limiting Lp graphon.
- Compactness proof: The martingale limit W lies in Lp, satisfies the inherited norm bound, and the original sequence converges to W in cut metric.The argument derives Lp convergence of the step approximations before concluding cut-metric convergence of the original sequence.
4. Regularity lemma for Lp upper regular graph(on)s
The paper proves weak regularity lemmas for Lp upper regular graphons and weighted graphs. The proofs preserve lower bounds on partition sizes and use truncation when p<2 to overcome the failure of direct L2 energy arguments.
- Proof obstacles: The proof faces two obstacles: refinement may create parts smaller than η, and for p<2 the L2 increment argument lacks a suitable norm bound.Both issues arise while attempting to iteratively reduce cut-norm error.
- Proof strategy: Small parts are handled by replacing sets S,T with nearby S′,T′ so every refined part has measure at least η while the cut discrepancy remains above Cε/2.Lemma 4.2 controls the effect of these modifications on the relevant inner products.
- Graphon theorem: For a (C,η)-upper Lp regular graphon, a partition into at most 4^N parts, each of measure at least η, achieves cut error at most Cε.Here N=(6/ε)^max{2,p/(p−1)} and η=4^(-N−1)(ε/160)^(p/(p−1)).
- Proof strategy: The graphon proof iteratively refines partitions by at most four subparts while maintaining the lower-size condition, stopping once the cut error is at most Cε.If refinement continued beyond N steps, the norm and energy bounds would yield a contradiction.
- Proof strategy: For p<2, truncating the final step function restores the energy-increment argument needed to force termination of the partition refinement process.The construction uses the truncated graphon to recover a usable increment estimate.
- Weighted graphs: The same weak regularity conclusion extends to (C,η)-upper Lp regular weighted graphs, with each part having weight at least ηα_G.The weighted-graph theorem uses the corresponding atomicity constraints in the graphon representation.
5. Limit of an Lp upper regular sequence
The section establishes limits for Lp upper regular graph sequences and clarifies when normalized cut convergence does or does not yield an Lp graphon limit. It also relates cut-distance convergence to vertex reorderings.
- Every Lp upper regular sequence with p > 1 has a subsequence converging to an Lp graphon.
- Without Lp upper regularity, a graph sequence may lack both a Cauchy subsequence and a graphon limit.
- The normalized graphs Gn/∥Gn∥1 form a cut-metric Cauchy sequence but converge to no graphon in cut distance.Their normalized graphons converge pointwise almost everywhere to zero, while each has integral 1.
- For upper regular sequences converging in cut distance to an Lp graphon U, vertices can be ordered so the associated graphons converge in cut norm.
- The integral cut distance is approximated by vertex permutations with error O(1/√log v), with the error scaling to 34K/√log v for edge weights in [−K,K].
6. W-random weighted graphs
This section proves that W-random weighted graphs recover their generating graphon in L1 almost surely. It uses finite partitions, equidistribution, and a strong-law estimate for U-statistics.
- For every integrable graphon W, d1(H(W,n),W) → 0 almost surely.
- Hoeffding’s theorem gives almost-sure convergence of the sampled graphon’s L1 norm to ∥W∥1.
- The proof approximates W by a finite equal-interval partition whose step graphon is close in L1.
- Almost-sure equidistribution of the sampled points makes the finite-partition random graph converge to its step graphon.
7. Sparse random graphs
The section develops sparse random graph convergence by proving almost-sure convergence results under integrability and mild edge-weight conditions. These results complete the random-model arrows connecting Lp graphons, graph sequences, and upper regular sequences.
- Theorem 2.14(b) proves almost-sure normalized cut convergence for sparse random graphs generated from graphons.
- The random graph construction is compared with W-random graphs generated from the same i.i.d. uniform sequence.
- Lemma 7.3 shows that sparsifying weighted graphs preserves normalized cut behavior when ρn → 0, nρn → ∞, total weight is uniformly bounded, and edge weights satisfy the stated mild condition.
- The section completes the arrows from Lp graphon limits to Lp upper regular sequences.
- Applying the lemma to H(W,n), together with convergence of its L1 norm, yields the sparse random graph conclusion.
8. Counting lemma for Lp graphons
This section establishes counting lemmas for Lp graphons using a generalized Hölder inequality and truncation of unbounded factors. It identifies p > Δ as the valid range and gives counterexamples at and below the maximum degree threshold.
- Generalized Hölder’s inequality supplies the integrability bound needed to control graphon homomorphism densities.
- A separable graphon example is finite in every Lp space below Δ but not in LΔ, demonstrating the threshold’s sharpness.
- For a graph F of maximum degree Δ, the counting lemma is proved under the condition p > Δ.
- When ∥U−W∥□ is small, the counting expressions differ by a term bounded through the truncated factors and the cut norm.
- Truncating U and W at level K separates bounded factors from tails, producing an error controlled by K and p−Δ.
- No counting lemma can hold when p ≤ Δ.
Appendix A. Lp upper regularity implies unbounded average degree
The appendix proves that C-upper Lp regularity forces the average degree of simple graphs to diverge. Its key estimate derives this from a maximal matching and upper regularity applied to a suitable vertex partition.
- |E(G_n)| / |V(G_n)| → ∞ as n → ∞ for every C-upper Lp regular sequence of simple graphs with p > 1.
- The proof reduces the claim to a lemma giving |E(G)| / |V(G)| ≥ cη^(-1+1/p) for sufficiently small η.
- A maximal matching supplies a vertex set A, and the proof establishes that its size is at least 2η_0n before applying upper regularity.
- Because every edge meets A, the partition {A, V \ A} controls the graph’s edges through upper regularity and convexity of x ↦ x^p.
- The argument then partitions the vertices so each edge lies within one part and invokes upper regularity together with convexity to complete the edge-count bound.
Appendix B. Proof of a Chernoff bound
The appendix proves a two-sided Chernoff bound by treating upper and lower deviations separately for independent Bernoulli variables, then combining the bounds with a union bound.
- Upper-tail and lower-tail deviations are analyzed separately by applying exponential bounds to Bernoulli variables and their negations.
- The exponential estimates produce bounds involving λ − (1 + λ) ln(1 + λ) and −λ / (1 + λ) + (1 − λ) ln(1 + λ).
- The same upper bound applies to the lower deviation after negating all variables, and a union bound combines the two cases.
Appendix C. Uniform upper regularity
Uniform upper regularity supplies the L1 framework needed to replace Lp boundedness, support compactness and convergence, and extend regularity results to L1 graphons and weighted graphs.
- For p = 1, uniform integrability replaces ordinary L1 boundedness because L1 norm bounds alone do not ensure the needed convergence behavior.
- A graphon has K-bounded tails when its mass above threshold K is uniformly controlled, and uniform integrability requires one common tail function across the set.
- Uniform upper regularity requires graphons to have K-bounded tails after every sufficiently fine partition, with η_n tending to zero along the sequence.
- Uniform upper regularity is preserved under cut-metric convergence, and graph sequences inherit the result when they have no dominant nodes.
- Every uniformly upper regular sequence of graphons or weighted graphs has a convergent subsequence under the normalized cut metric.
- The appendix develops weak regularity lemmas for graphons with bounded tails and for (K, η)-upper regular graphons, including equipartitions and bounded-size measurable partitions.
- Uniformly integrable closed sets of graphons are compact in the cut metric, with weak regularity and compactness established through truncation and martingale convergence.
- Uniformly upper regular simple-graph sequences also have diverging average degree, while L1 compactness requires uniform integrability because the L1 graphon ball is not compact in cut distance.