An Llog L theory of sparse graph convergence
Abstract
Borgs, Chayes, Cohn and Zhao developed a limit theory for sparse graphs based on Lp upper regularity with p>1, where Holder's inequality controls small sets. We develop the analogous theory in the Orlicz class Llog L, replacing Holder by the Young-Fenchel inequality for Ψ(u)=(1+u)log(1+u)−u and Ψ*(v)=ev−1−v. We prove a weak regularity lemma for upper Ψ-regular graphons with 4O(1/ε2) parts, using the modular ∫Ψ as the energy; that upper Ψ-regular sequences have cut-metric convergent subsequences; that convergent sequences with Llog L limits are upper Ψ-regular; and that Llog L balls are cut-metric compact. The class strictly contains every Lp class with p>1, and we give sparse W-random graphs that are upper Ψ-regular but not upper Lp regular for any p>1. For graphs with a given degree sequence we prove, by Stein's method of exchangeable pairs with switchings, that if the average degree tends to infinity, the density to zero and the degree profile converges in L1 to φ, uniformly random graphs converge in the normalized cut metric to φ⊗φ, with no condition on the maximum degree; the sequence is upper Ψ-regular when φ∈ Llog L. We also show that the maximum-entropy β-model is entrywise Chung-Lu when dmax2=o(M), and that cut-closeness to it follows from a lower bound e−o(M) on its probability of having the prescribed degrees. Finally, Ψ is the large deviation rate function of sparse Erdos-Renyi graphs up to a factor 1+O(1/log1/p).
Related
- Spectral Convergence of Sparse Bipartite Graphs via the Line-Graphon
- Two-point concentration for graph classes admitting sparse vertex deletion
- New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
- Local Convergence of Triadic Closures of Sparse Random Graphs
- Quantum dynamics on the sparse Erdős-Rényi graph
BibTeX
@misc{mehrdad2026llog,
title = {{An $L\log L$ theory of sparse graph convergence}},
author = {Behzad Mehrdad},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02187},
eprint = {2611.02187},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02187},
}
RIS
TY - UNPB
TI - An Llog L theory of sparse graph convergence
AU - Behzad Mehrdad
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02187
UR - https://arxiv.org/abs/2611.02187
AB - Borgs, Chayes, Cohn and Zhao developed a limit theory for sparse graphs based on L^p upper regularity with p>1, where Holder's inequality controls small sets. We develop the analogous theory in the Orlicz class Llog L, replacing Holder by the Young-Fenchel inequality for Ψ(u)=(1+u)log(1+u)−u and Ψ^*(v)=e^v−1−v. We prove a weak regularity lemma for upper Ψ-regular graphons with 4^O(1/ε^2) parts, using the modular ∫Ψ as the energy; that upper Ψ-regular sequences have cut-metric convergent subsequences; that convergent sequences with Llog L limits are upper Ψ-regular; and that Llog L balls are cut-metric compact. The class strictly contains every L^p class with p>1, and we give sparse W-random graphs that are upper Ψ-regular but not upper L^p regular for any p>1. For graphs with a given degree sequence we prove, by Stein's method of exchangeable pairs with switchings, that if the average degree tends to infinity, the density to zero and the degree profile converges in L^1 to φ, uniformly random graphs converge in the normalized cut metric to φ⊗φ, with no condition on the maximum degree; the sequence is upper Ψ-regular when φ∈ Llog L. We also show that the maximum-entropy β-model is entrywise Chung-Lu when d_max^2=o(M), and that cut-closeness to it follows from a lower bound e^−o(M) on its probability of having the prescribed degrees. Finally, Ψ is the large deviation rate function of sparse Erdos-Renyi graphs up to a factor 1+O(1/log1/p).
ER -