Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

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.

 

Two critical periods in the evolution of random planar graphs
HTML articles powered by AMS MathViewer

by Mihyun Kang and Tomasz Łuczak PDF
Trans. Amer. Math. Soc. 364 (2012), 4239-4265 Request permission

Abstract:

Let $P(n,M)$ be a graph chosen uniformly at random from the family of all labeled planar graphs with $n$ vertices and $M$ edges. In this paper we study the component structure of $P(n,M)$. Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of $P(n,M)$. The first one, of width $\Theta (n^{2/3})$, is analogous to the phase transition observed in the standard random graph models and takes place for $M=n/2+O(n^{2/3})$, when the largest complex component is formed. Then, for $M=n+O(n^{3/5})$, when the complex components cover nearly all vertices, the second critical period of width $n^{3/5}$ occurs. Starting from that moment increasing of $M$ mostly affects the density of the complex components, not its size.
References
Similar Articles
Additional Information
  • Mihyun Kang
  • Affiliation: Institut für Optimierung und Diskrete Mathematik (Math B), Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria
  • Email: kang@math.tugraz.at
  • Tomasz Łuczak
  • Affiliation: Department of Discrete Mathematics, Adam Mickiewicz University, 61-614 Poznań, Poland
  • Email: tomasz@amu.edu.pl
  • Received by editor(s): June 2, 2010
  • Received by editor(s) in revised form: November 5, 2010
  • Published electronically: March 13, 2012
  • © Copyright 2012 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 364 (2012), 4239-4265
  • MSC (2010): Primary 05C10, 05C80; Secondary 05C30, 05A16
  • DOI: https://doi.org/10.1090/S0002-9947-2012-05502-4
  • MathSciNet review: 2912453