Matchings of exponential tail on coin flips in Z^d

  • Date: 03/28/2007

Adam Timar (University of British Columbia)


University of British Columbia


We construct a translation-invariant matching between vertices of
different labels of Bernoulli(1/2) percolation on Z^d, in such a way
that the probability that a vertex is at distance > r from its pair
decays as an exponential function of the d-2'nd power of r. Our method
implies earlier results about matching n uniformly distributed red
points with n uniformly distributed blue points in the unit square with
minimal average distance. Other consequences to invariant matchings in
R^d and optimal matchings in the unit cube are also presented.

Other Information: 

Probability Seminar 2007