2020/12/13 by Alexander E. Holroyd, Svante Janson, Holroyd, Alexander E. +3 · 1 citation
Mathematics · #05C70 #60D05 #60G55 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2012.07129
openalex publication_date 2020/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose that red and blue points form independent homogeneous Poisson processes of equal intensity in Rd. For a positive (respectively, negative) parameter γ we consider red-blue matchings that locally minimize (respectively, maximize) the sum of γth powers of the edge lengths, subject to locally minimizing the number of unmatched points. The parameter can be viewed as a measure of fairness. The limit γ→-∞ is equivalent to Gale-Shapley stable matching. We also consider limits as γ approaches 0, 1-, 1+ and ∞. We focus on dimension d=1. We prove that almost surely no such matching has unmatched points. (This question is open for higher d). For each γ<1 we establish that there is almost surely a unique such matching, and that it can be expressed as a finitary factor of the points. Moreover, its typical edge length has finite rth moment if and only if r<1/2. In contrast, for γ=1 there are uncountably many matchings, while for γ>1 there are countably many, but it is impossible to choose one in a translation-invariant way. We obtain existence results in higher dimensions (covering many but not all cases). We address analogous questions for one-colour matchings also.