Shift-coupling of random rooted graphs and networks

DOI10.1090/CONM/719/14474zbMATH Open1423.60027arXiv1703.06619OpenAlexW2964023207MaRDI QIDQ5236809FDOQ5236809

Authors: Ali Khezeli 

Publication date: 16 October 2019

Published in: Unimodularity in Randomly Generated Graphs (Search for Journal in Brave)

Abstract: In this paper, we present a result similar to the shift-coupling result of Thorisson (1996) in the context of random graphs and networks. The result is that a given random rooted network can be obtained by changing the root of another given one if and only if the distributions of the two agree on the invariant sigma-field. Several applications of the result are presented for the case of unimodular networks. In particular, it is shown that the distribution of a unimodular network is uniquely determined by its restriction to the invariant sigma-filed. Also, the theorem is applied to the existence of an invariant transport kernel that balances between two given (discrete) measures on the vertices. An application is the existence of a so called extra head scheme for the Bernoulli process on an infinite unimodular graph. Moreover, a construction is presented for balancing transport kernels that is a generalization of the Gale-Shapley stable matching algorithm in bipartite graphs. Another application is on a general method that covers the situations where some vertices and edges are added to a unimodular network and then, to make it unimodular, the probability measure is biased and then a new root is selected. It is proved that this method provides all possible unimodularizations in these situations. Finally, analogous existing results for stationary point processes and unimodular networks are discussed in detail.

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

Recommendations

• Invariance, quasi-invariance, and unimodularity for random graphs
• Extra heads and invariant allocations
• Processes on unimodular random networks
• Invariant Schreier decorations of unimodular random networks
• Strong couplings for static locally tree-like random graphs

zbMATH Keywords

random graphsunimodularityrandom networksshift-couplinginvariant transportsnetwork extensionstable transportsunimodularization

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Special processes (60K99)

Cites Work

• Stochastic and Integral Geometry
• Processes on unimodular random networks
• Ergodic Equivalence Relations, Cohomology, and Von Neumann Algebras. I
• Title not available (Why is that?)
• Station�re zuf�llige Ma�e auf lokalkompakten Abelschen Gruppen
• College Admissions and the Stability of Marriage
• Extra heads and invariant allocations
• A stable marriage of Poisson and Lebesgue
• Invariant transports of stationary random measures and mass-stationarity
• Title not available (Why is that?)
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Stable transports between stationary random measures
• Indistinguishability of percolation clusters
• Groups of Automorphisms of Borel Spaces
• Group-invariant percolation on graphs
• Trees and matchings from point processes
• Representation of invariant measures
• Unimodular random trees
• Transforming random elements and shifting random fields
• Eternal Family Trees and dynamics on unimodular random graphs

Cited In (9)

• A strong duality principle for equivalence couplings and total variation
• Equidecomposition in cardinal algebras
• Coupling from the past for the null recurrent Markov chain
• Non-intersection of transient branching random walks
• Processes on unimodular random networks
• Doeblin trees
• Counterexamples for percolation on unimodular random graphs
• Unimodular Hausdorff and Minkowski dimensions
• Counter examples to invariant circle packing

This page was built for publication: Shift-coupling of random rooted graphs and networks

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