Prof. dr. Michael Drmota: The maximum degree of planar graphs
Datum objave: 7. 12. 2012
Matematični kolokvij
Četrtek, 13. 12. 2012, ob 18:15 v predavalnici 2.02 na Jadranski 21.
Michael Drmota
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.
