Monday, November 17th, 2014 | 4pm-5pm | Burnside 1205 |

McGill University

On the diameter of random planar graphs

We show that the diameter of a random planar graph of size n chosen uniformly is equal to n^{1/4+o(1)} with high probability. This result builds on the fact that random planar maps (=embedded planar graphs) are very well understood and that the two models coincide at the 3-connected level via Whitney's embedding theorem. Rather than focusing on (heavy) technical details I will try to explain how this works, focusing on the description of {1,2,3}-connected components and their sizes, and saying a few words about the (extremely active) topic of random planar maps. I'll say a word on higher genus surfaces if I have time (joint work with Eric Fusy, Omer Gimenez, and Marc Noy).