Multigraph limits and exchangeability

DOI10.1007/S10474-010-0037-3MaRDI QIDQ626051zbMATH OpenOpenAlexFDO

Authors Juan-Miguel Gracia

Publication date 25 February 2011

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.0547

zbMATH Keywords

convergence in distributiondense graphsexchangeabilitygraphonsmultigraphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Exchangeability for stochastic processes (60G09)

Abstract: The theory of limits of dense graph sequences was initiated by Lovasz and Szegedy. We give a possible generalization of this theory to multigraphs. Our proofs are based on the correspondence between dense graph limits and countable, exchangeable arrays of random variables observed by Diaconis and Janson. The main ingredient in the construction of the limit object is Aldous' representation theorem for exchangeable arrays.

Review text

The theory of limits of dense graph sequences was initiated by \textit{L. Lovász and B. Szegedy} [J. Comb. Theory, Ser. B 96, No.\,6, 933--957 (2006; Zbl 1113.05092)]. We give a possible generalization of this theory to multigraphs. Our proofs are based on the correspondence between dense graph limits and countable, exchangeable arrays of random variables observed by \textit{P. Diaconis and S. Janson} [Rend. Mat. Appl., VII. Ser. 28, No. ~1, 33--61 (2008; Zbl 1162.60009)]. The main ingredient in the construction of the limit object is Aldous' representation theorem for exchangeable arrays, see \textit{D. J. Aldous} [J. Multivariate Anal. 11, 581--598 (1981; Zbl 0474.60044)].

Recommendations

• Multigraph limit of the dense configuration model and the preferential attachment graph
• Limits of dense graph sequences
• Poset limits and exchangeable random posets
• Measures on the square as sparse graph limits
• Multigraph limits, unbounded kernels, and Banach space decorated graphs

Cites work

• Graph limits and exchangeable random graphs
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 3237398 (Why is no real title available?)
• Limits of dense graph sequences
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Probabilistic Symmetries and Invariance Principles
• Probability with Martingales
• Representations for partially exchangeable arrays of random variables

Cited in

(11)

• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• Exchangeability and continuum limits of discrete random structures
• Time evolution of dense multigraph limits under edge-conservative preferential attachment dynamics
• Graph limits and exchangeable random graphs
• Multigraph limit of the dense configuration model and the preferential attachment graph
• Harmonic analysis of symmetric random graphs.
• Limits of multi-relational graphs
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• Probability-graphons: limits of large dense weighted graphs
• Exchangeable interval hypergraphs and limits of ordered discrete structures
• On exchangeable random variables and the statistics of large graphs and hypergraphs

This page was built for publication: Multigraph limits and exchangeability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626051)