Minimal matchings of point processes

DOI10.1007/S00440-022-01151-YzbMATH Open1500.60006arXiv2012.07129OpenAlexW3111979666MaRDI QIDQ2089762FDOQ2089762

Authors: A. E. Holroyd, Svante Janson, Johan Wästlund 

Publication date: 24 October 2022

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: Suppose that red and blue points form independent homogeneous Poisson processes of equal intensity in $R^d$. For a positive (respectively, negative) parameter $gamma$ we consider red-blue matchings that locally minimize (respectively, maximize) the sum of $gamma$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 $gammao-infty$ is equivalent to Gale-Shapley stable matching. We also consider limits as $gamma$ approaches $0$, $1-$, $1+$ and $infty$. 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 $gamma<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 $r$th moment if and only if $r<1/2$. In contrast, for $gamma=1$ there are uncountably many matchings, while for $gamma>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.

Full work available at URL: https://arxiv.org/abs/2012.07129

Recommendations

• Poisson matching
• Geometric properties of Poisson matchings
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Hyperuniform and rigid stable matchings
• Multicolour Poisson matching

zbMATH Keywords

point processmatchingPoisson processstationary process

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Geometric probability and stochastic geometry (60D05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Title not available (Why is that?)
• On optimal matchings
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• College Admissions and the Stability of Marriage
• Title not available (Why is that?)
• Insertion and deletion tolerance of point processes
• Optimal transport from Lebesgue to Poisson
• Poisson matching
• A stable marriage of Poisson and Lebesgue
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Geometric properties of Poisson matchings
• Trees and matchings from point processes
• Descending chains, the lilypond model, and mutual-nearest-neighbour matching
• Greedy Matching on the Line
• Bipartite stable Poisson graphs on \(\mathbb R\)
• Stable Poisson graphs in one dimension
• Percolation in invariant Poisson graphs with i.i.d. degrees
• Random measures, theory and applications
• The number of optimal matchings for Euclidean assignment on the line
• Gravitational allocation on the sphere
• Finer estimates on the \(2\)-dimensional matching problem
• Correlation function for the grid-Poisson Euclidean matching on a line and on a circle
• The Dyck bound in the concave 1-dimensional random assignment model
• Random assignment problems on \(2d\) manifolds
• On the optimal map in the 2-dimensional random matching problem
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Friendly frogs, stable marriage, and the magic of invariance

Cited In (10)

• Translation-equivariant matchings of coin flips on \(\mathbb Z^d\)
• Bipartite stable Poisson graphs on \(\mathbb R\)
• Invariant bipartite random graphs on \(\mathbb R^{d}\)
• Multicolour Poisson matching
• There is no stationary \(p\)-cyclically monotone Poisson matching in 2d
• There is no stationary cyclically monotone Poisson matching in 2d
• A factor matching of optimal tail between Poisson processes
• Hyperuniform and rigid stable matchings
• On spatial matchings: the first-in-first-match case
• Geometric properties of Poisson matchings

This page was built for publication: Minimal matchings of point processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2089762)