Stable Poisson graphs in one dimension

DOI10.1214/EJP.V16-897MaRDI QIDQ638434zbMATH OpenFDO

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

Publication date 9 September 2011

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

Full work available at URL https://arxiv.org/abs/1101.3716, http://www.emis.de/journals/EJP-ECP/_ejpecp/viewarticle73e0.html

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)

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.

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

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)