Stable Poisson graphs in one dimension

DOI10.1214/EJP.V16-897zbMATH Open1228.60109arXiv1101.3716MaRDI QIDQ638434FDOQ638434

Authors: Maria Deijfen, A. E. Holroyd, Yuval Peres 

Publication date: 9 September 2011

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: Let each point of a homogeneous Poisson process on $RR$ independently be equipped with a random number of stubs (half-edges) according to a given probability distribution $mu$ on the positive integers. We consider schemes based on Gale-Shapley stable marriage for perfectly matching the stubs to obtain a simple graph with degree distribution $mu$. We prove results on the existence of an infinite component and on the length of the edges, with focus on the case $mu(2)=1$. In this case, for the random direction stable matching scheme introduced by Deijfen and Meester we prove that there is no infinite component, while for the stable matching of Deijfen, H"aggstr"om and Holroyd we prove that existence of an infinite component follows from a certain statement involving a {em finite} interval, which is overwhelmingly supported by simulation evidence.

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

Recommendations

• On the one dimensional Poisson random geometric graph
• Bipartite stable Poisson graphs on \(\mathbb R\)
• ON STABLE GRAPHS
• scientific article; zbMATH DE number 4063144
• Stable graphs: distributions and line-breaking construction
• On the stable degree of graphs
• On regular-stable graphs
• A note on stability of graphs
• Composite graphs with stability index one

zbMATH Keywords

matchingrandom graphPoisson processpercolationdegree distribution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Cited In (9)

• Bipartite stable Poisson graphs on \(\mathbb R\)
• Invariant bipartite random graphs on \(\mathbb R^{d}\)
• Long paths and connectivity in 1-independent random graphs
• On percolation in one-dimensional stable Poisson graphs
• Percolation for the stable marriage of Poisson and Lebesgue with random appetites
• 1‐independent percolation on ℤ2×Kn
• Friendly frogs, stable marriage, and the magic of invariance
• Minimal matchings of point processes
• Hyperuniform and rigid stable matchings

This page was built for publication: Stable Poisson graphs in one dimension

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