Poisson Matching
By Alexander E. Holroyd, Robin Pemantle, Yuval Peres, Oded Schramm. 2007
80 citations recorded by the source corpus.
Suppose that red and blue points occur as independent homogeneous Poisson processes in Rd. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d = 1, 2, the matching distance X from a typical point to its partner must have infinite d/2-th moment, while in dimensions d ≥ 3 there exist schemes where X has finite exponential moments. The Gale-Shapley stable marriage is one natural matching scheme, obtained by iteratively matching mutually closest pairs. A principal result of this paper is a power law upper bound on the matching distance X for this scheme. A power law lower bound holds also. In particular, stable marriage is close to optimal (in tail behavior) in d = 1, but far from optimal in d ≥ 3. For the problem of matching Poisson points of a single color to each other, in d = 1 there exist schemes where X has finite exponential moments, but if we insist that the matching is a deterministic factor of the point process then X must have infinite mean.
Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/ae9a3e818f743948132ab64ad9a26a088eff33aa
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
In Mathematical Physics
In Statistics and Probability
Citations in the corpus
- Insertion and deletion tolerance of point processes (2010, background): “nt and has no descending chains. If R or B is deletion-tolerant or insertion-tolerant, then the two-colour stable matching scheme satisfies E∗Xd = ∞. Theorems 7 and 8 strengthen the earlier results in [9] in the following ways. In [9], Theorem 7 is proved in the case of homogeneous Poisson processes,”
- Combinatorial Optimization Over Two Random Point Sets (2011, unknown): “Now, the fact that for 0 < p < 2d, limn n p dEMp({Xi}i=1, {Yi}i=1) = βp(d) implies the tightness of the sequence of matchings σn and it can be used to define a stationary matching σ on (Ξ1,Ξ2), see the proof of Theorem 1 (iii) in [6] for the details of such an argument.”