The probability of planarity of a random graph near the critical point

Abstract : Erdős and Rényi conjectured in 1960 that the limiting probability $p$ that a random graph with $n$ vertices and $M=n/2$ edges is planar exists. It has been shown that indeed p exists and is a constant strictly between 0 and 1. In this paper we answer completely this long standing question by finding an exact expression for this probability, whose approximate value turns out to be $p ≈0.99780$. More generally, we compute the probability of planarity at the critical window of width $n^{2/3}$ around the critical point $M=n/2$. We extend these results to some classes of graphs closed under taking minors. As an example, we show that the probability of being series-parallel converges to 0.98003. Our proofs rely on exploiting the structure of random graphs in the critical window, obtained previously by Janson, Łuczak and Wierman, by means of generating functions and analytic methods. This is a striking example of how analytic combinatorics can be applied to classical problems on random graphs.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.791-802, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229657
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:25
Dernière modification le : jeudi 11 janvier 2018 - 06:17:42
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:31:33

Fichier

dmAS0167.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229657, version 1

Collections

Citation

Marc Noy, Vlady Ravelomanana, Juanjo Rué. The probability of planarity of a random graph near the critical point. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.791-802, 2013, DMTCS Proceedings. 〈hal-01229657〉

Partager

Métriques

Consultations de la notice

45

Téléchargements de fichiers

147