Drmota, Michael; Matematični kolokvij december 2012

Iz MaFiRaWiki

The maximum degree of planar graphs

Michael Drmota

Technische Universität Wien

13. december 2012

McDiarmid and Reed showed in 2008 that the maximum degree Δn of a random labeled planar graph with n vertices satisfies with high probability c1logn < Δn < c2logn 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) > | Δnclogn | = O(loglogn) for a constant c \approx 2.52946 that can be determined explicitly. The proof combines tools from analytic combinatorics and Boltzmann sampling techniques.

This is joint work with Omer Gimenez, Marc Noy, Konstantinos Panagiotou, and Angelika Steger.

Glej tudi

Matematični kolokviji

Osebna orodja