Prof. dr. Michael Drmota: The maximum degree of planar graphs
Source: Mathematics colloquium
Technische Universität Wien
McDiarmid and Reed showed in 2008 that the maximum degree Δ n of a random labeled planar graph with n vertices satisfies with high probability c1 log n < Δ n < c2 log n for suitable constants 0 < c1 < c2. The purpose of this talk is to make this statement more accurate by showing that the precise limiting behavior of Δ n is (with high probability) > ∣Δ n − c log n∣ = O(log log n) for a constant c ≈ 2. 52946 that can be determined explicitly. The proof combines tools from analytic combinatorics and Boltzmann sampling techniques.