×
Deijfen, Maria; Häggström, Olle; Holroyd, Alexander E.

Percolation in invariant Poisson graphs with i.i.d. degrees. (English) Zbl 1254.05181

Ark. Mat. 50, No. 1, 41-58 (2012).
Summary: Let each point of a homogeneous Poisson process in \(\mathbb{R}^d\) independently be equipped with a random number of stubs (half-edges) according to a given probability distribution \(\mu\) on the positive integers. We consider translation-invariant schemes for perfectly matching the stubs to obtain a simple graph with degree distribution \(\mu\). Leaving aside degenerate cases, we prove that for any \(\mu\) there exist schemes that give only finite components as well as schemes that give infinite components. For a particular matching scheme which is a natural extension of Gale-Shapley stable marriage, we give sufficient conditions on \(\mu\) for the absence and presence of infinite components.

Cited in 1 Review
Cited in 2 Documents

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C07 Vertex degrees
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
60K35 Interacting random processes; statistical mechanics type models; percolation theory

Keywords:

matching schema; point processes; Palm probability
PDF BibTeX XML Cite
\textit{M. Deijfen} et al., Ark. Mat. 50, No. 1, 41--58 (2012; Zbl 1254.05181)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] Benjamini, I., Lyons, R., Peres, Y. and Schramm, O., Group-invariant percolation on graphs, Geom. Funct. Anal. 9 (1999), 29–66. · Zbl 0924.43002
[2] Bollobás, B., Janson, S. and Riordan, O., The phase transition in inhomogeneous random graphs, Random Structures Algorithms 31 (2006), 3–122. · Zbl 1123.05083
[3] Britton, T., Deijfen, M. and Martin-Löf, A., Generating simple random graphs with prescribed degree distribution, J. Stat. Phys. 124 (2005), 1377–1397. · Zbl 1106.05086
[4] Chung, F. and Lu, L., Connected components in random graphs with given expected degree sequences, Ann. Comb. 6 (2002), 125–145. · Zbl 1009.05124
[5] Chung, F. and Lu, L., The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. USA 99 (2002), 15879–15882. · Zbl 1064.05137
[6] Daley, D. and Last, G., Descending chains, the lilypond model, and mutual nearest neighbour matching, Adv. in Appl. Probab. 37 (2005), 604–628. · Zbl 1078.60038
[7] Deijfen, M., Stationary random graphs with prescribed i.i.d. degrees on a spatial Poisson process, Electron. Commun. Probab. 14 (2009), 81–89. · Zbl 1185.05126
[8] Deijfen, M. and Jonasson, J., Stationary random graphs on \(\mathbb{Z}\) with prescribed i.i.d. degrees and finite mean connections, Electron. Commun. Probab. 11 (2006), 336–346. · Zbl 1127.05093
[9] Deijfen, M. and Meester, R., Generating stationary random graphs on \(\mathbb{Z}\) with prescribed i.i.d. degrees, Adv. in Appl. Probab. 38 (2006), 287–298. · Zbl 1102.05054
[10] Gale, D. and Shapely, L., College admissions and stability of marriage, Amer. Math. Monthly 69 (1962), 9–15. · Zbl 0109.24403
[11] Gilbert, L., On the cost of generating an equivalence relation, Ergodic Theory Dynam. Systems 15 (1995), 1173–1181. · Zbl 0843.28010
[12] Häggström, O. and Meester, R., Nearest neighbor and hard sphere models in continuum percolation, Random Structures Algorithms 9 (1996), 295–315. · Zbl 0866.60088
[13] Holroyd, A., Pemantle, R., Peres, Y. and Schramm, O., Poisson matching, Ann. Inst. Henri Poincaré Probab. Stat. 45 (2009), 266–287. · Zbl 1175.60012
[14] Holroyd, A. and Peres, Y., Trees and matchings from point processes, Electron. Commun. Probab. 8 (2003), 17–27. · Zbl 1060.60048
[15] Jonasson, J., Invariant random graphs with i.i.d. degrees in a general geography, Probab. Theory Related Fields 143 (2009), 643–656. · Zbl 1170.05055
[16] Kallenberg, O., Foundations of Modern Probability, Springer, Berlin, 1997. · Zbl 0892.60001
[17] Liggett, T., Schonmann, R. and Stacey, M., Domination by product measures, Ann. Probab. 25 (1997), 71–95. · Zbl 0882.60046
[18] Molloy, M. and Reed, B., A critical point for random graphs with a given degree sequence, Random Structures Algorithms 6 (1995), 161–179. · Zbl 0823.05050
[19] Molloy, M. and Reed, B., The size of the giant component of a random graphs with a given degree sequence, Combin. Probab. Comput. 7 (1998), 295–305. · Zbl 0916.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.