The degree distribution of random planar graphs

The degree distribution of random planar graphs

Tue, 24/05/2011
14:30 		Angelika Steger (ETH Zurich) Combinatorial Theory Seminar Add to calendar L3
The degree distribution of random planar graphs
A random planar graph $ P_n $ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $ n $ vertices. In this talk we show that with probability $ 1-o(1) $ the number of vertices of degree $ k $ in $ P_n $ is very close to a quantity $ d_k n $ that we determine explicitly. Here $ k=k(n) \le c \log n $. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)