uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Heavy subtrees of Galton-Watson trees with an application to Apollonian networks
McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
McGill Univ, Sch Comp Sci, 3480 Univ St, Montreal, PQ H3A 0E9, Canada;Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
2019 (English)In: Electronic Journal of Probability, ISSN 1083-6489, E-ISSN 1083-6489, Vol. 24, p. 1-44, article id 2Article in journal (Refereed) Published
Abstract [en]

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 en 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 Omega(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.

Place, publisher, year, edition, pages
UNIV WASHINGTON, DEPT MATHEMATICS , 2019. Vol. 24, p. 1-44, article id 2
Keywords [en]
branching processes, fringe trees, spine decomposition, binary trees, continuum random tree, Brownian excursion, exponential functionals, Apollonian networks
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-377981DOI: 10.1214/19-EJP263ISI: 000458519800001OAI: oai:DiVA.org:uu-377981DiVA, id: diva2:1293414
Available from: 2019-03-04 Created: 2019-03-04 Last updated: 2019-03-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Holmgren, Cecilia

Search in DiVA

By author/editor
Holmgren, Cecilia
By organisation
Department of Mathematics
In the same journal
Electronic Journal of Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf