Minimal matchings of point processes

DOI10.1007/S00440-022-01151-YMaRDI QIDQ2089762zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)