Longest paths in random apollonian networks and largest r-ary subtrees of random d-ary recursive trees

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Let r and d be positive integers with r < d. Consider a random d-ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random leaf and give it d newly created offspring. Let Td,t be the tree produced after t steps. We show that there exists a fixed δ < 1 depending on d and r such that almost surely for all large t , every r-ary subtree of Td,t has less than tδ vertices. The proof involves analysis that also yields a related result. Consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. In this way, one face is destroyed and three new faces are created. After t steps, we obtain a random triangulated plane graph with t + 3 vertices, which is called a random Apollonian network. We prove that there exists a fixed δ < 1, such that eventually every path in this graph has length less than tδ , which verifies a conjecture of Cooper and Frieze (2015).

Original languageEnglish
Pages (from-to)846-856
Number of pages11
JournalJournal of Applied Probability
Volume53
Issue number3
DOIs
Publication statusPublished - 1 Sep 2016

Keywords

  • Eggenberger-Pólya urn
  • Longest path
  • Random apollonian network
  • Random d-ary recursive tree

Cite this