Trees and Matchings from Point Processes
By Alexander E. Holroyd, Yuval Peres. 2002
64 citations recorded by the source corpus.
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.
Subfields: Applied Mathematics, Computer Graphics and Computer-Aided Design, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/f9ea295c08ecfaa285c13bb1f9c161e0489f8163
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Günter Last
- Yuval Peres
- Hermann Thorisson
- Robin Pemantle
- Oded Schramm
- Alexander E. Holroyd
- Russell Lyons
- Sourav Chatterjee
In Computer Graphics and Computer-Aided Design
- Russell Lyons
- David J. Aldous
- Robin Pemantle
- Oded Schramm
- Yuval Peres
- Alexander E. Holroyd
- Charles Bordenave
- Pietro Caputo
In Mathematical Physics
- Russell Lyons
- Yuval Peres
- Günter Last
- Robin Pemantle
- Oded Schramm
- Hermann Thorisson
- Alexander E. Holroyd
- Dan Romik
Citations in the corpus
- Processes on Unimodular Random Networks (2006, background): “For a few recent examples, see Benjamini and Schramm (2001a), Holroyd and Peres (2003), or Timár (2004).”
- Poisson Matching (2007, methodology): “(Similar constructions were used in [6] and [13]).”
- Invariant transports of stationary random measures and mass-stationarity (2009, background): “The question of whether the external randomization could be removed from the definition inspired considerable research activity; see [4, 10, 14, 29].”
- Gravitational allocation to Poisson points (2006, background): “(iii) For some results on the related topic of translation-invariant perfect matchings for point processes, see [9].”
- Extra heads and invariant allocations (2003, background): “Related questions involving stable matchings of point processes were studied in [6].”