## Poisson Matching

- Date: 03/12/2007

Alexander Holroyd (University of British Columbia)

University of British Columbia

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.

Probability Seminar 2007