Geodesic
The probability of planarity of a random graph near the critical point
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2013_special_264_a27,
     author = {Noy, Marc and Ravelomanana, Vlady and Ru\'e, Juanjo},
     title = {The probability of planarity of a random graph near the critical point},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)},
     year = {2013},
     doi = {10.46298/dmtcs.2343},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2343/}
}
TY  - JOUR
AU  - Noy, Marc
AU  - Ravelomanana, Vlady
AU  - Rué, Juanjo
TI  - The probability of planarity of a random graph near the critical point
JO  - Discrete mathematics & theoretical computer science
PY  - 2013
VL  - DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2343/
DO  - 10.46298/dmtcs.2343
LA  - en
ID  - DMTCS_2013_special_264_a27
ER  - 
%0 Journal Article
%A Noy, Marc
%A Ravelomanana, Vlady
%A Rué, Juanjo
%T The probability of planarity of a random graph near the critical point
%J Discrete mathematics & theoretical computer science
%D 2013
%V DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2343/
%R 10.46298/dmtcs.2343
%G en
%F DMTCS_2013_special_264_a27
Noy, Marc; Ravelomanana, Vlady; Rué, Juanjo. The probability of planarity of a random graph near the critical point. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) (2013). doi : 10.46298/dmtcs.2343. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2343/

Cité par Sources :