## Two critical periods in the evolution of random planar graphs

### Authors:

- Mihyun Kang,
- Tomasz Łuczak

### 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 Θ(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. © 2012 American Mathematical Society.

- Record ID
- UAMcd3c5c2eacbe4204bad252a0641ce71f
- Author
- Journal series
- Transactions of the American Mathematical Society, ISSN 0002-9947
- Issue year
- 2012
- Vol
- 364
- Pages
- 4239-4265
- ASJC Classification
- ;
- DOI
- DOI:10.1090/S0002-9947-2012-05502-4 opening in a new tab
- Language
- en English
- Score (nominal)
- 35
- Score source
- journalList
- Publication indicators
- = 12.000; : 2012 = 1.698; : 2012 = 1.019 (2) - 2012=1.126 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAMcd3c5c2eacbe4204bad252a0641ce71f/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back