Strong couplings for static locally tree-like random graphs

2021/02/21 by Mariana Olvera‐Cravioto, Olvera-Cravioto, Mariana · 1 citation
Computer Science · Mathematics · #05C80 #60J80 #Bayesian Methods and Mixture Models #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2102.10673

openalex publication_date 2021/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The goal of this paper is to provide a general purpose result for the coupling of exploration processes of random graphs, both undirected and directed, with their local weak limits when this limit is a marked Galton-Watson process. This class includes in particular the configuration model and the family of inhomogeneous random graphs with rank-1 kernel. Vertices in the graph are allowed to have attributes on a general separable metric space and can potentially influence the construction of the graph itself. The coupling holds for any fixed depth of a breadth-first exploration process.

Cited by

• Explosive connectivity and mechanical rigidity in cubic lattice structures

Related

• Local weak limit of dynamical inhomogeneous random graphs
• Local limit of the random degree constrained process
• Branching random walks and contact processes on Galton-Watson trees
• The Contact Process on Random Graphs and Galton-Watson Trees
• The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees