{
  "id": "1611.07466",
  "version": "v1",
  "published": "2016-11-22T19:10:07.000Z",
  "updated": "2016-11-22T19:10:07.000Z",
  "title": "Depth of vertices with high degree in random recursive trees",
  "authors": [
    "Laura Eslava"
  ],
  "comment": "25 pages, 3 figures",
  "categories": [
    "math.PR",
    "cs.DS"
  ],
  "abstract": "Let $T_n$ be a random recursive tree with $n$ nodes. List vertices of $T_n$ in decreasing order of degree as $v^1,\\ldots,v^n$, and write $d^i$ and $h^i$ for the degree of $v^i$ and the distance of $v^i$ from the root, respectively. We prove that, as $n \\to \\infty$ along suitable subsequences, \\[ \\bigg(d^i - \\lfloor \\log_2 n \\rfloor, \\frac{h^i - \\mu\\ln n}{\\sqrt{\\sigma^2\\ln n}}\\bigg) \\to ((P_i,i \\ge 1),(N_i,i \\ge 1))\\, , \\] where $\\mu=1-(\\log_2 e)/2$, $\\sigma^2=1-(\\log_2 e)/4$, $(P_i,i \\ge 1)$ is a Poisson point process on $\\mathbb{Z}$ and $(N_i,i \\ge 1)$ is a vector of independent standard Gaussians. We additionally establish joint normality for the depths of uniformly random vertices in $T_n$, which extends previous results from Devroye and Mahmoud. The joint holds even if the random vertices are conditioned to have large degree, provided the normalization is adjusted accordingly. Our results are based on a simple relationship between random recursive trees and Kingman's $n$-coalescent; a utility that seems to have been largely overlooked.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-11-22T19:10:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80"
    ],
    "keywords": [
      "random recursive tree",
      "high degree",
      "poisson point process",
      "independent standard gaussians",
      "joint holds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}