Poisson Matching

Red points and blue points occur as independent Poisson processes in R^d, and we consider schemes to perfectly match red points to blue points in a translation-invariant way. For any matching scheme in dimensions 1 and 2, the distance X from a typical red point to its blue partner has infinite d/2-th moment, while in dimensions >=3 there exist schemes where X has exponential tails. For the variant problem of matching points of a single colour to each other, there exist schemes where X has exponential tails, but if we insist that the matching is a deterministic factor of the points then in dimension 1, X must have infinite mean. The Gale-Shapley stable marriage is a natural greedy matching scheme. It is close to optimal (in terms of X) for two-colour matching in dimension 1, but far from optimal for dimensions >=3 and for one-colour matching.

Joint work with Robin Pemantle, Yuval Peres and Oded Schramm.