{
  "id": "0712.1867",
  "version": "v3",
  "published": "2007-12-12T06:27:08.000Z",
  "updated": "2008-03-15T05:05:49.000Z",
  "title": "Poisson Matching",
  "authors": [
    "Alexander E. Holroyd",
    "Robin Pemantle",
    "Yuval Peres",
    "Oded Schramm"
  ],
  "comment": "37 pages; to appear in Annales de l'institut Henri Poincare (B)",
  "categories": [
    "math.PR"
  ],
  "abstract": "Suppose that red and blue points occur as independent homogeneous Poisson processes in R^d. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1,2, the matching distance X from a typical point to its partner must have infinite d/2-th moment, while in dimensions d>=3 there exist schemes where X has finite exponential moments. The Gale-Shapley stable marriage is one natural matching scheme, obtained by iteratively matching mutually closest pairs. A principal result of this paper is a power law upper bound on the matching distance X for this scheme. A power law lower bound holds also. In particular, stable marriage is close to optimal (in tail behavior) in d=1, but far from optimal in d>=3. For the problem of matching Poisson points of a single color to each other, in d=1 there exist schemes where X has finite exponential moments, but if we insist that the matching is a deterministic factor of the point process then X must have infinite mean.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2008-03-15T05:05:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60D05",
      "60G55",
      "05C70"
    ],
    "keywords": [
      "poisson matching",
      "finite exponential moments",
      "matching mutually closest pairs",
      "power law lower bound holds",
      "power law upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0712.1867H"
    }
  }
}