Premium
The maximum degree of random planar graphs
Author(s) -
Drmota M.,
Giménez O.,
Noy M.,
Panagiotou K.,
Steger A.
Publication year - 2014
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/pdu024
Subject(s) - mathematics , combinatorics , degree (music) , planar graph , random graph , planar , graph , binary logarithm , discrete mathematics , constant (computer programming) , physics , computer graphics (images) , computer science , acoustics , programming language
McDiarmid and Reed [‘On the maximum degree of a random planar graph’, Combin. Probab. Comput . 17 (2008) 591–601] showed that the maximum degree Δ n of a random labeled planar graph with n vertices satisfies with high probability (w.h.p.)c 1 log n < Δ n < c 2 log n , for suitable constants. In this paper, we determine the precise asymptotics, showing in particular that w.h.p.| Δ n − c log n | = O ( log log n ) ,for a constant c ≈ 2 . 52946 that we determine explicitly. The proof combines tools from analytic combinatorics and Boltzmann sampling techniques.