Metraipolis › archive › dc_7a14ea0bedab

An $L\log L$ theory of sparse graph convergence — arXiv:2611.02187

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.02187
License (as archived): CC0-1.0
Archived: 2026-11-03T18:47:28.317Z
SHA-256 of the archived text: 208446b2a5dc4ada10e5be4cae9030b2638f06c346579ebc61c180ffba1ea4a5
Stable URL of this page: https://metraipolis.com/documento/dc_7a14ea0bedab

How to cite

An $L\log L$ theory of sparse graph convergence — arXiv:2611.02187 — arXiv (en), https://arxiv.org/abs/2611.02187 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a14ea0bedab (Metraipolis archive dc_7a14ea0bedab, sha256 208446b2a5dc4ada10e5be4cae9030b2638f06c346579ebc61c180ffba1ea4a5)

BibTeX

@misc{dc7a14ea0bedab,
  title = {An $Llog L$ theory of sparse graph convergence — arXiv:2611.02187},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02187},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a14ea0bedab; sha256 208446b2a5dc4ada10e5be4cae9030b2638f06c346579ebc61c180ffba1ea4a5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02187. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $L\log L$, replacing Holder by the Young-Fenchel inequality for $\Psi(u)=(1+u)\log(1+u)-u$ and $\Psi^*(v)=e^v-1-v$. We prove a weak regularity lemma for upper $\Psi$-regular graphons with $4^{O(1/\varepsilon^2)}$ parts, using the modular $\int\Psi$ as the energy; that upper $\Psi$-regular sequences have cut-metric convergent subsequences; that convergent sequences with $L\log L$ limits are upper $\Psi$-regular; and that $L\log 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 $\Psi$-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 $\varphi$, uniformly random graphs converge in the normalized cut metric to $\varphi\otimes\varphi$, with no condition on the maximum degree; the sequence is upper $\Psi$-regular when $\varphi\in L\log L$. We also show that the maximum-entropy $\beta$-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, $\Psi$ is the large deviation rate function of sparse Erdos-Renyi graphs up to a factor $1+O(1/\log\frac1p)$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.02187 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:07.722Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).