Poisson Matching

  • Date: 03/12/2007
Lecturer(s):

Alexander Holroyd (University of British Columbia)

Location: 

University of British Columbia

Topic: 

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.

Other Information: 

Probability Seminar 2007

Sponsor: 

pims