Heavy subtrees of Galton-Watson trees with an application to Apollonian networks

Luc Devroye, Cecilia Holmgren, Henning Sulzbach

Research output: Contribution to journalArticlepeer-review

128 Downloads (Pure)

Abstract

We study heavy subtrees of conditional Galton-Watson trees. In a standard Galton-Watson tree conditional on its size being n, we order all children by their subtree sizes, from large (heavy) to small. A node is marked if it is among the k heaviest nodes among its siblings. Unmarked nodes and their subtrees are removed, leaving only a tree of marked nodes, which we call the k-heavy tree. We study various properties of these trees, including their size and the maximal distance from any original node to the k-heavy tree. In particular, under some moment condition, the 2-heavy tree is with high probability larger than cn for some constant c>0, and the maximal distance from the k-heavy tree is O(n 1/(k+1)) in probability. As a consequence, for uniformly random Apollonian networks of size n, the expected size of the longest simple path is Ω(n). We also show that the length of the heavy path (that is, k=1) converges (after rescaling) to the corresponding object in Aldous’ Brownian continuum random tree.

Original languageEnglish
Article number2
Number of pages44
JournalElectronic Journal of Probability
Volume24
DOIs
Publication statusPublished - 5 Feb 2019

Keywords

  • branching processes
  • fringe trees
  • spine decomposition
  • binary trees
  • continuum random trees
  • Brownian excursion
  • exponential functionals
  • Apollonian networks

Fingerprint

Dive into the research topics of 'Heavy subtrees of Galton-Watson trees with an application to Apollonian networks'. Together they form a unique fingerprint.

Cite this