### 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 *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

*r*-ary subtree of

*T*has less than

_{d,t}*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 (from-to) | 846-856 |

Number of pages | 11 |

Journal | Journal of Applied Probability |

Volume | 53 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Sep 2016 |

### Keywords

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