{
  "id": "1610.08786",
  "version": "v1",
  "published": "2016-10-27T14:07:39.000Z",
  "updated": "2016-10-27T14:07:39.000Z",
  "title": "Parking on a random tree",
  "authors": [
    "Christina Goldschmidt",
    "Michał Przykucki"
  ],
  "comment": "18 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Consider a uniform random rooted tree on vertices labelled by $[n] = \\{1,2,\\ldots,n\\}$, with edges directed towards the root. We imagine that each node of the tree has space for a single car to park. A number $m \\le n$ of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider $m =[\\alpha n]$ and let $A_{n,\\alpha}$ denote the event that all $[\\alpha n]$ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if $\\alpha \\le 1/2$, we have $\\mathbb{P}(A_{n,\\alpha}) \\to \\frac{\\sqrt{1-2\\alpha}}{1-\\alpha}$, whereas if $\\alpha > 1/2$ we have $\\mathbb{P}(A_{n,\\alpha}) \\to 0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we are led to consider the following variant of the problem: take the tree to be the family tree of a Galton-Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson($\\alpha$) number of cars arrive at each vertex. Let $X$ be the number of cars which visit the root of the tree. Then for $\\alpha \\le 1/2$, we have $\\mathbb{E}[X] \\leq 1$, whereas for $\\alpha > 1/2$, we have $\\mathbb{E}[X] = \\infty$. This discontinuous phase transition turns out to be a generic phenomenon in settings with an arbitrary offspring distribution of mean at least 1 for the tree and arbitrary arrival distribution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-27T14:07:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60J80",
      "05C05",
      "82B26"
    ],
    "keywords": [
      "random tree",
      "empty space",
      "arbitrary arrival distribution",
      "uniform random rooted tree",
      "discontinuous phase transition turns"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}