Asymptotic enumeration and limit laws for graphs of fixed genus - Mathematics > CombinatoricsReport as inadecuate




Asymptotic enumeration and limit laws for graphs of fixed genus - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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.



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

Source: https://arxiv.org/



DOWNLOAD PDF




Related documents