On the Diameter and Longest Paths in Random Apollonian Networks
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 6486|
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. After n-3 steps, we obtain a random triangulated plane graph with n vertices, which is called a random Apollonian network. Asymptotically almost surely, the diameter of the resulting network is is asymptotic to c log n, where c ~ 1.668, and the longest path length is at most n^δ for some δ<1.
The latter result refutes a conjecture of Frieze and Tsourakakis, and confirms a conjecture of Cooper and Frieze. For its proof, we bound the size of the largest regular (r-ary) subtrees of the random recursive tree with t vertices.
Includes joint work with Andrea Collevecchio, Ehsan Ebrahimzadeh, Linda Farczadi, Pu Gao, Abbas Mehrabian, Cristiane M. Sato, Jonathan Zung.
200 University Avenue West
Waterloo, ON N2L 3G1