AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

60 Minutes

Saarbrücken

In the 1960s, in his series of fundamental “census” papers, Tutte founded the enumerative theory of planar maps. Since then, the theory has grown enormously, extending to maps on surfaces, to unembedded graphs on surfaces, and to minor-closed classes of graphs. We will pay particular attention to properties of random planar graphs, and discuss basic parameters and also extremal parameters like maximum degree, diameter, and largest k-connected components. For instance, with high probability a random (labelled) planar graph with n vertices has 2.21*n edges, a connected component containing n-O(1) vertices, a block (2-connected component) containing 0.96*n vertices, maximum degree 2.53*log(n), and diameter of order roughly n1/4. The talk will be kept at a non-technical level, giving at some point brief indications on the tools needed from complex analysis.

Benjamin Doerr

--email hidden

passcode not visible

logged in users only

Kolkom 2010