An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions

C Borgs, J Chayes, H Cohn, Y Zhao - Transactions of the American …, 2019 - ams.org
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 …

Large deviations of subgraph counts for sparse Erdős–Rényi graphs

N Cook, A Dembo - Advances in Mathematics, 2020 - Elsevier
For any fixed simple graph H=(V, E) and any fixed u> 0, we establish the leading order of the
exponential rate function for the probability that the number of copies of H in the Erdős …

Action convergence of operators and graphs

Á Backhausz, B Szegedy - Canadian Journal of Mathematics, 2022 - cambridge.org
We present a new approach to graph limit theory that unifies and generalizes the two most
well-developed directions, namely dense graph limits (even the more general limits) and …

A graphon approach to limiting spectral distributions of Wigner‐type matrices

Y Zhu - Random Structures & Algorithms, 2020 - Wiley Online Library
We present a new approach, based on graphon theory, to finding the limiting spectral
distributions of general Wigner‐type matrices. This approach determines the moments of the …

Probability graphons: the right convergence point of view

G Zucal - arXiv preprint arXiv:2407.05998, 2024 - arxiv.org
We extend the theory of probability graphons, continuum representations of edge-decorated
graphs arising in graph limits theory, to the'right convergence'point of view. First of all, we …

[HTML][HTML] Measures on the square as sparse graph limits

D Kunszenti-Kovács, L Lovász, B Szegedy - Journal of Combinatorial …, 2019 - Elsevier
We study a metric on the set of finite graphs in which two graphs are considered to be similar
if they have similar bounded dimensional “factors”. We show that limits of convergent graph …

Local convergence for permutations and local limits for uniform -avoiding permutations with

J Borga - Probability Theory and Related Fields, 2020 - Springer
We set up a new notion of local convergence for permutations and we prove a
characterization in terms of proportions of consecutive pattern occurrences. We also …

Approximating sparse graphs: The random overlapping communities model

S Petti, SS Vempala - Random Structures & Algorithms, 2022 - Wiley Online Library
How can we approximate sparse graphs and sequences of sparse graphs (with unbounded
average degree)? We consider convergence in the first k moments of the graph spectrum …

Probability graphons and P-variables: two equivalent viewpoints for dense weighted graph limits

G Zucal - arXiv preprint arXiv:2408.07572, 2024 - arxiv.org
We develop further the graph limit theory for dense weighted graph sequences. In particular,
we consider probability graphons, which have recently appeared in graph limit theory as …

Approximating sparse graphs: The random overlapping communities model

S Petti, SS Vempala - arXiv preprint arXiv:1802.03652, 2018 - arxiv.org
How can we approximate sparse graphs and sequences of sparse graphs (with unbounded
average degree)? We consider convergence in the first $ k $ moments of the graph …