Asymptotic enumeration and limit laws for graphs of fixed genus - Mathematics > CombinatoricsReportar como inadecuado




Asymptotic enumeration and limit laws for graphs of fixed genus - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: It is shown that the number of labelled graphs with n vertices that can beembedded in the orientable surface S g of genus g grows asymptotically like$c^{g}n^{5g-1-2-1}\gamma^n n!$ where $c^{g}>0$, and $\gamma \approx27.23$ is the exponential growth rate of planar graphs. This generalizes theresult for the planar case g=0, obtained by Gimenez and Noy.An analogous result for non-orientable surfaces is obtained. In addition, itis proved that several parameters of interest behave asymptotically as in theplanar case. It follows, in particular, that a random graph embeddable in S ghas a unique 2-connected component of linear size with high probability.



Autor: Guillaume Chapuy, Eric Fusy, Omer Gimenez, Bojan Mohar, Marc Noy

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados