{
  "id": "2201.11773",
  "version": "v1",
  "published": "2022-01-27T19:37:42.000Z",
  "updated": "2022-01-27T19:37:42.000Z",
  "title": "Random trees have height $O(\\sqrt{n})$",
  "authors": [
    "Louigi Addario-Berry",
    "Serte Donderwinkel"
  ],
  "comment": "35 pages,6 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We obtain new non-asymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaym\\'e trees (the family trees of branching processes). In particular, we settle two conjectures of Janson (2012), two conjectures of Addario-Berry, Devroye and Janson (2013), and a conjecture of Addario-Berry (2019). Moreover, we define a partial ordering on degree sequences and show that it induces a stochastic ordering on the heights of uniformly random trees with given degree sequences. The latter result settles a conjecture of Addario-Berry, Donderwinkel, Maazoun and Martin (2021), and can also be used to show that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves. Our proofs are based in part on a bijection introduced by Addario-Berry, Donderwinkel, Maazoun and Martin (2021), which can be recast to provide a line-breaking construction of random trees with given vertex degrees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-01-27T19:37:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C05"
    ],
    "keywords": [
      "degree sequence",
      "uniformly random trees",
      "conjecture",
      "addario-berry",
      "non-asymptotic tail bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}