Abstract
Suppose that red and blue points occur as independent Poisson processes of equal intensity in \({\mathbb {R}^d}\), and that the red points are matched to the blue points via straight edges in a translation-invariant way. We address several closely related properties of such matchings. We prove that there exist matchings that locally minimize total edge length in d = 1 and d ≥ 3, but not in the strip \({\mathbb {R}\times[0,1]}\). We prove that there exist matchings in which every bounded set intersects only finitely many edges in d ≥ 2, but not in d = 1 or in the strip. It is unknown whether there exists a matching with no crossings in d = 2, but we prove positive answers to various relaxations of this question. Several open problems are presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Deijfen M.: Stationary random graphs with prescribed iid degrees on a spatial Poisson process. Electron. Commun. Probab. 14, 81–89 (2009)
Gale D., Shapley L.: College admissions and stability of marriage. Am. Math. Mon. 69(1), 9–15 (1962)
Holroyd A.E., Pemantle R., Peres Y., Schramm O.: Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat. 45(1), 266–287 (2009)
Holroyd A.E., Peres Y.: Trees and matchings from point processes. Electron. Comm. Probab. 8, 17–27 (2003) electronic
Kallenberg, O.: Foundations of modern probability. In: Probability and its Applications (New York), 2nd edn. Springer, New York (2002)
Krikun M.: Connected allocation to Poisson points in R 2. Electron. Comm. Probab. 12, 140–145 (2007) electronic
Meshalkin, L.D.: A case of isomorphism of Bernoulli schemes. Sov. Math. Dokl. 3 (1962)
Soo, T.: Translation-invariant matchings of coin-flips on Z d. Adv. Appl. Probab. (to appear). arXiv:math/0610334
Timar, A.: Invariant matchings of exponential tail on coin flips in Z d (preprint)
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Oded Schramm, 10 December 1961–1 September 2008.
Funded in part by Microsoft and NSERC.
Rights and permissions
About this article
Cite this article
Holroyd, A.E. Geometric properties of Poisson matchings. Probab. Theory Relat. Fields 150, 511–527 (2011). https://doi.org/10.1007/s00440-010-0282-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-010-0282-y