{
  "id": "2102.05852",
  "version": "v1",
  "published": "2021-02-11T05:32:13.000Z",
  "updated": "2021-02-11T05:32:13.000Z",
  "title": "Expected number of induced subtrees shared by two independent copies of the terminal tree in a critical branching process",
  "authors": [
    "Boris Pittel"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Consider a rooted tree $T$ of minimum degree $2$ at least, with leaf-set $[n]$. A rooted tree $\\mathcal T$ with leaf-set $S\\subset [n]$ is induced by $S$ in $T$ if $\\mathcal T$ is the lowest common ancestor subtree for $S$, with all its degree-2 vertices suppressed. A \"maximum agreement subtree\" (MAST) for a pair of two trees $T'$ and $T''$ is a tree $\\mathcal T$ with a largest leaf-set $S\\subset [n]$ such that $\\mathcal T$ is induced by $S$ both in $T'$ and $T''$. Bryant et al. \\cite{BryMcKSte} and Bernstein et al. \\cite{Ber} proved, among other results, that for $T'$ and $T''$ being two independent copies of a random binary (uniform or Yule-Harding distributed) tree $T$, the likely magnitude order of $\\text{MAST}(T',T'')$ is $O(n^{1/2})$. In this paper we prove this bound for a wide class of random rooted trees: $T$ is a terminal tree of a branching process with an offspring distribution of mean $1$, conditioned on \"total number of leaves is $n$\".",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-02-11T05:32:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "05C80",
      "05C05",
      "34E05",
      "60C05"
    ],
    "keywords": [
      "independent copies",
      "terminal tree",
      "critical branching process",
      "expected number",
      "induced subtrees"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}