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

exchangeabilitymultigraphsconvergence in distributiondense graphsgraphons

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graph representations (geometric and intersection representations, etc.) (05C62) 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.

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

• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 3237398 (Why is no real title available?)
• Graph limits and exchangeable random graphs
• 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)

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

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)