Vorträge in der Woche 31.05.2010 bis 06.06.2010

Montag, 31.05.2010: Random Planar Graphs: Combinatorics and Asymptotics

Prof. Dr. Michael Drmota

The study of random planar graphs has started only few years ago by A. Denise, M. Vasconcellos and D. J. A. Welsh in 1996. Since then much attention has been payed to this topic. A ground-breaking result was obtained recently by O. Gimenez and M. Noy by solving the long-standing open problem of getting precise estimates for the number of planar graphs, drawing on previous work by Bender et al. The purpose of this talk is to present first a survey on asymptotic properties of random planar graphs and related graph structures (series-parallel graphs, embeddable graphs etc.) We will then focus on the combinatorics behind these problems (combinatorial decompositions, relations for generating functions) and analytic methods for obtaining asymptotics and probabilistic limit theorems for parameters of interest. A special focus will be on the asymptotic degree distribution and on the maximum degree. For example, a result that has been obtained jointly with Gimenez and Noy says, that the probability that a random node in a large random planar graph has degree k converges to p(k), where the generating function of the numbers p(k) can be explicitly stated and, as k to infinity, p(k) is asymptotically equal to c (k power (-0,5)) (R power k) for some positive constant c and some constant R strictly between 0 and 1.