Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 8 (2003) > Paper 3 open journal systems 


Trees and Matchings from Point Processes

Alexander E. Holroyd, University of California, Berkeley
Yuval Peres, University of California, Berkeley


Abstract
A factor graph of a point process is a graph whose vertices are the points of the process, and which is constructed from the process in a deterministic isometry-invariant way. We prove that the d-dimensional Poisson process has a one-ended tree as a factor graph. This implies that the Poisson points can be given an ordering isomorphic to the usual ordering of the integers in a deterministic isometry-invariant way. For d greater than or equal to 4 our result answers a question posed by Ferrari, Landim and Thorisson [7]. We prove also that any isometry-invariant ergodic point process of finite intensity in Euclidean or hyperbolic space has a perfect matching as a factor graph provided all the inter-point distances are distinct.


Full text: PDF

Pages: 17-27

Published on: March 3, 2003
Bibliography
  1. S. Adams and R. Lyons, Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations, Israel J. Math., 75(2-3), (1991) 341--370. Math. Review 93j:43001
  2. S. R. Adams and R. J. Spatzier, Kazhdan groups, cocycles and trees, Amer. J. Math., 112(2), (1990) 271--287. Math. Review 91c:22011
  3. D. Aldous and J. M. Steele, Asymptotics for Euclidean minimal spanning trees on random points, Probab. Theory Related Fields, 92(2), (1992) 247--258. Math. Review 93c:60007
  4. K. S. Alexander, Percolation and minimal spanning forests in infinite graphs, Ann. Probab., 23(1), (1995) 87--104. Math. Review 96c:60114
  5. I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Group-invariant percolation on graphs, Geom. Funct. Anal., 9(1), (1999) 29--66. Math. Review 99m:60149
  6. I. Benjamini and O. Schramm, Percolation in the hyperbolic plane, J. Amer. Math. Soc., 14(2) (2001) 487--507 (electronic). Math. Review 2002h:82049
  7. P. A. Ferrari, C. Landim, and H. Thorisson, Poisson trees, succession lines and coalescing random walks, Preprint. Math. Review number not available.
  8. D. Gale and L. Shapley, College admissions and stability of marriage, Amer. Math. Monthly, 69(1), (1962) 9--15. Math. Review number not available.
  9. O. Haggstrom, Infinite clusters in dependent automorphism invariant percolation on trees, Ann. Probab., 25(3), (1997) 1423--1436. Math. Review 98f:60207
  10. O. Haggstrom and R. Meester, Nearest neighbor and hard sphere models in continuum percolation, Random Structures Algorithms, 9(3), (1996) 295--315. Math. Review 99c:60217
  11. R. Pemantle and Y. Peres, Nonamenable products are not treeable, Israel J. Math., 118, (2000) 147--155. Math. Review 2001j:43002
  12. J. M. Steele, Probability theory and combinatorial optimization, volume 69 of CBMS-NSF Regional Conference Series in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1997). Math. Review 99d:60002
  13. H. Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications. Springer-Verlag, New York (2000). Math. Review 2001b:60003
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X