Asymptotic enumeration and limit laws for graphs of fixed genus

Guillaume Chapuy; Eric Fusy; Omer Giménez; Bojan Mohar; Marc Noy

hal-00713480, version 1

Asymptotic enumeration and limit laws for graphs of fixed genus

Guillaume Chapuy ¹, Eric Fusy () ², Omer Giménez ³, Bojan Mohar ¹, Marc Noy ³

Journal of Combinatorial Theory. Series A 118, 3 (2011) 748--777

Abstract: It is shown that the number of labelled graphs with $n$ vertices that can be embedded in the orientable surface $\mathbb{S}_g$ of genus $g$ grows asymptotically like $ c^{(g)}n^{5(g-1)/2-1}\gamma^n n! $, where $c^{(g)} >0$, and $\gamma \approx 27.23$ is the exponential growth rate of planar graphs. This generalizes the result for the planar case $g=0$, obtained by Giménez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in $\mathbb{S}_g$ has a unique 2-connected component of linear size with high probability.

1: Department of Mathematics
Simon Fraser University
2: Laboratoire d'informatique de l'école polytechnique (LIX)
CNRS : UMR7161 – Polytechnique - X
3: Universitat Politècnica de Catalunya (UPC)
Universitat Politécnica de Catalunya

hal-00713480, version 1
http://hal.archives-ouvertes.fr/hal-00713480
oai:hal.archives-ouvertes.fr:hal-00713480
From: Guillaume Chapuy <>
Submitted on: Sunday, 1 July 2012 17:17:56
Updated on: Sunday, 1 July 2012 17:17:56

See detailed view

Associated documents

DOI: 10.1016/j.jcta.2010.11.014

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="hal-00713480"><analytic>
<author><persName><forename>Guillaume</forename><surname>Chapuy</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics</orgName>
<country>CA</country>
<orgName type="institution">Simon Fraser University</orgName>
</affiliation>
</author>
<author><persName><forename>Eric</forename><surname>Fusy</surname></persName>
<affiliation>
<orgName type="laboratory">LIX</orgName>
<orgName type="team">Laboratoire d'informatique de l'école polytechnique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7161</orgName>
<orgName type="institution">Polytechnique - X</orgName>
</affiliation>
</author>
<author><persName><forename>Omer</forename><surname>Giménez</surname></persName>
<affiliation>
<orgName type="laboratory">UPC</orgName>
<orgName type="team">Universitat Politècnica de Catalunya</orgName>
<country>ES</country>
<orgName type="institution">Universitat Politécnica de Catalunya</orgName>
</affiliation>
</author>
<author><persName><forename>Bojan</forename><surname>Mohar</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics</orgName>
<country>CA</country>
<orgName type="institution">Simon Fraser University</orgName>
</affiliation>
</author>
<author><persName><forename>Marc</forename><surname>Noy</surname></persName>
<affiliation>
<orgName type="laboratory">UPC</orgName>
<orgName type="team">Universitat Politècnica de Catalunya</orgName>
<country>ES</country>
<orgName type="institution">Universitat Politécnica de Catalunya</orgName>
</affiliation>
</author>
<title type="main" level="a">Asymptotic enumeration and limit laws for graphs of fixed genus</title></analytic><monogr><title level="j" type="main">Journal of Combinatorial Theory. Series A</title><imprint><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="vol">118</biblScope><biblScope type="issue">3</biblScope><biblScope type="pp">748--777</biblScope></imprint></monogr><idno type="doi">10.1016/j.jcta.2010.11.014</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00713480</idno></biblStruct>
</listBibl>
</listBibl>