{
  "id": "math/0507324",
  "version": "v1",
  "published": "2005-07-18T08:04:16.000Z",
  "updated": "2005-07-18T08:04:16.000Z",
  "title": "Tail Bounds for the Stable Marriage of Poisson and Lebesgue",
  "authors": [
    "Christopher Hoffman",
    "Alexander E. Holroyd",
    "Yuval Peres"
  ],
  "comment": "30 pages, 2 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "Let \\Xi be a discrete set in R^d. Call the elements of \\Xi centers. The well-known Voronoi tessellation partitions R^d into polyhedral regions (of varying volumes) by allocating each site of R^d to the closest center. Here we study allocations of R^d to \\Xi in which each center attempts to claim a region of equal volume \\alpha. We focus on the case where \\Xi arises from a Poisson process of unit intensity. It was proved in math.PR/0505668 that there is a unique allocation which is stable in the sense of the Gale-Shapley marriage problem. We study the distance X from a typical site to its allocated center in the stable allocation. The model exhibits a phase transition in the appetite \\alpha. In the critical case \\alpha=1 we prove a power law upper bound on X in dimension d=1. It is an open problem to prove any upper bound in d\\geq 2. (Power law lower bounds were proved in math.PR/0505668 for all d). In the non-critical cases \\alpha<1 and \\alpha>1 we prove exponential upper bounds on X.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-07-18T08:04:16.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60D05"
    ],
    "keywords": [
      "tail bounds",
      "stable marriage",
      "power law lower bounds",
      "well-known voronoi tessellation partitions",
      "power law upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......7324H"
    }
  }
}