Projects per year
Abstract
Let r and d be positive integers with r < d. Consider a random dary tree constructed as follows. Start with a single vertex, and in each timestep choose a uniformly random leaf and give it d newly created offspring. Let T_{d,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 rary subtree of T_{d,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 language  English 

Pages (fromto)  846856 
Number of pages  11 
Journal  Journal of Applied Probability 
Volume  53 
Issue number  3 
DOIs  
Publication status  Published  1 Sep 2016 
Keywords
 EggenbergerPólya urn
 Longest path
 Random apollonian network
 Random dary recursive tree
Projects
 2 Finished

Finite Markov chains in statistical mechanics and combinatorics
Garoni, T., Collevecchio, A. & Markowsky, G.
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research

Advances in the analysis of random structures and their applications: relationships among models
Australian Research Council (ARC)
1/08/12 → 31/12/17
Project: Research