Probability Seminar: Abbas Mehrabian

  • Date: 10/05/2016
  • Time: 15:00
Abbas Mehrabian, UBC Computer Science and PIMS

University of British Columbia


On longest paths and diameter in random Apollonian networks


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. After n – 3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). See for an example.

We prove that the diameter of a RAN is asymptotic to c log(n) in probability, where c ≈ 1.668 is the solution of an explicit equation. The proof adapts a technique of Broutin and Devroye for estimating the height of random trees.

We also prove that there exists a fixed s<1, such that eventually every self-avoiding walk in this graph has length less than n^s, which verifies a conjecture of Cooper and Frieze. Using a similar technique, we show that if r < d are fixed constants, then every r-ary subtree of a random d-ary recursive tree on n vertices has less than n^b vertices, for some b=b(d,r)<1.

Based on joint work with A. Collevecchio, E. Ebrahimzadeh, L. Farczadi, P. Gao, C. Sato, N. Wormald, and J. Zung.

Other Information: 

Loacation: ESB 2012