{
  "id": "2108.04989",
  "version": "v1",
  "published": "2021-08-11T02:04:13.000Z",
  "updated": "2021-08-11T02:04:13.000Z",
  "title": "Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves",
  "authors": [
    "Miklós Bóna",
    "Boris Pittel"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that for any fixed $k$, the probability that a random vertex of a random increasing plane tree is of rank $k$, i.e. at vertex-distance $k$ from the leaves, converges to a constant $c_k$ as the size $n$ of the tree goes to infinity. We prove a similar result for randomly selected $r$-tuples of vertices that shows that the ranks of a finite uniformly random set of vertices are asymptotically independent. We compute the exact value of $c_k$ for $0\\leq k\\leq 3$, demonstrating that the limiting expected fraction of vertices with rank $\\le 3$ is $0.9997\\dots$. In general, the distribution $\\{c_k\\}$ is quasi-Poisson, i.e. $c_k=O(1/(k-2)!)$. We prove that with high probability, the highest rank of a vertex in the tree is sandwiched between $\\log n / (\\log(\\log n))$ and $1.5\\log n/(\\log(\\log n))$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-08-11T02:04:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A16",
      "05C05",
      "06B05",
      "05C80",
      "05D40",
      "60C05"
    ],
    "keywords": [
      "random increasing plane tree",
      "asymptotic enumeration",
      "finite uniformly random set",
      "random vertex",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}