Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

ISSN 1088-6834 (online) ISSN 0894-0347 (print)

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

Asymptotic enumeration and limit laws of planar graphsHTML articles powered by AMS MathViewer

by Omer Giménez and Marc Noy
J. Amer. Math. Soc. 22 (2009), 309-329
DOI: https://doi.org/10.1090/S0894-0347-08-00624-3
Published electronically: October 17, 2008

Abstract:

We present a complete analytic solution to the problem of counting planar graphs. We prove an estimate $g_n \sim g\cdot n^{-7/2} \gamma ^n n!$ for the number $g_n$ of labelled planar graphs on $n$ vertices, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random planar graphs is asymptotically normal with linear mean and variance and, as a consequence, the number of edges is sharply concentrated around its expected value. Moreover we prove an estimate $g(q)\cdot n^{-4}\gamma (q)^n n!$ for the number of planar graphs with $n$ vertices and $\lfloor qn \rfloor$ edges, where $\gamma (q)$ is an analytic function of $q$. We also show that the number of connected components in a random planar graph is distributed asymptotically as a shifted Poisson law $1+P(\nu )$, where $\nu$ is an explicit constant. Additional Gaussian and Poisson limit laws for random planar graphs are derived. The proofs are based on singularity analysis of generating functions and on perturbation of singularities.
References
Similar Articles
• Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 05A16, 05C30, 05C10
• Retrieve articles in all journals with MSC (2000): 05A16, 05C30, 05C10
Bibliographic Information
• Omer Giménez
• Affiliation: Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain
• Email: Omer.Gimenez@upc.edu
• Marc Noy
• Affiliation: Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034 Barcelona, Spain
• Email: Marc.Noy@upc.edu
• Received by editor(s): August 3, 2005
• Published electronically: October 17, 2008
• Additional Notes: The first author’s research was supported in part by Project MTM2005-08618C02-01.