Stable Poisson Graphs in One Dimension

Maria Deijfen (Stockholm University)
Alexander E. Holroyd (Microsoft Research)
Yuval Peres (Microsoft Research)


Let each point of a homogeneous Poisson process on R 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äggström and Holroyd we prove that existence of an infinite component follows from a certain statement involving a finite interval, which is overwhelmingly supported by simulation evidence

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1238-1253

Publication Date: July 6, 2011

DOI: 10.1214/EJP.v16-897


  1. Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (1999): Group-invariant percolation on graphs, Geom. Funct. Anal. 9, 29-66. Math. Review 2002b:05121
  2. Bollobas, B. and Stacey, A. (1997): Approximate upper bounds for the critical probability of oriented percolation in two dimensions based on rapidly mixing Markov chains, J. Appl. Probab. 34, 859-867. Math. Review 99j:60152
  3. Deijfen, M. (2009): Stationary random graphs with prescribed i.i.d. degrees on a spatial Poisson process, Electr. Comm. Probab. 14, 81-89. Math. Review 2010e:05274
  4. Deijfen, M., Häggström, O. and Holroyd, A. (2010): Percolation in invariant Poisson graphs with i.i.d. degrees, Ark. Mat., to appear.
  5. Deijfen, M. and Meester, R. (2006): Generating stationary random graphs on Z with prescribed i.i.d. degrees, Adv. Appl. Probab. 38, 287-298. Math. Review 2007k:05197
  6. Gale, D. and Shapely, L. (1962): College admissions and stability of marriage, Amer. Math. Monthly 69, 9-15. Math. Review MR1531503
  7. Häggström, O. and Meester, R. (1996): Nearest neighbor and hard sphere models in continuum percolation, Rand. Struct. Alg. 9, 295-315. Math. Review 99c:60217
  8. Holroyd, A., Pemantle, R., Peres, Y. and Schramm, O. (2008): Poisson matching, Ann. Inst. Henri Poincare 45, 266-287. Math. Review 2010j:60122
  9. Holroyd, A. and Peres, Y. (2003): Trees and matchings from point processes, Elect. Comm. Probab. 8, 17-27. Math. Review 2004b:60127
  10. Kallenberg, O. (1997): Foundations of Modern Probability, Springer. Math. Review 99e:60001
  11. Riordan, O. and Walters, M. (2007): Rigorous confidence intervals for critical probabilities, Phys. Rev. E 76, 011110.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.