Longest paths in random Apollonian networks and largest \(r\)-ary subtrees of random \(d\)-ary recursive trees (Q2836235)

Consider the following iterative process for constructing a random planar triangulation: start with a single triangle; in each successive step, choose a bounded face uniformly at random, add a vertex inside that face and connect it to the vertices of that face to form three new faces. After \(t\) steps, this gives a random triangulated planar graph with \(t + 3\) vertices. Confirming a conjecture of \textit{C. Cooper} and \textit{A. Frieze} [``Long paths in random Apollonian networks'', Preprint, \url{arXiv:1404.2425}], the main result of this paper says that there exists \(\delta < 1\) such that eventually every path in this graph has length less than \(t^{\delta}\).NEWLINENEWLINEThe paper also contains a similar result pertaining to the following model of a random \(d\)-ary tree: start with a single vertex; in each successive step, choose a leaf of the tree uniformly at random and give it \(d\) offspring. If \(r < d\), the authors show that there exists \(\delta < 1\) depending only on \(d\) and \(r\) such that almost surely, for all large \(t\), every \(r\)-ary subtree of the random tree produced after \(t\) steps has fewer than \(t^\delta\) vertices.