Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Noy, M.; Ravelomanana, V.; Rue, J.
Tipus d'activitat
Article en revista
Revista
Proceedings of the American Mathematical Society
Data de publicació
2015-03-01
Volum
143
Número
3
Pàgina inicial
925
Pàgina final
936
Repositori
http://arxiv.org/pdf/1204.3376v2.pdf Obrir en finestra nova
http://hdl.handle.net/2117/83733 Obrir en finestra nova
URL
http://www.ams.org/journals/proc/2015-143-03/S0002-9939-2014-12141-1/S0002-9939-2014-12141-1.pdf Obrir en finestra nova
Resum
Let G(n, M) be the uniform random graph with n vertices and M edges. Erdos and Renyi (1960) conjectured that the limiting probability; lim(n ->infinity) Pr{G(n, n/2) is planar}; exists and is a constant strictly between 0 and 1. Luczak, Pittel and Wierman (1994) proved this conjecture, and Janson, Luczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact limiting probability of a random graph being planar near the critical point M = n/...
Citació
Noy, M., Ravelomanana, V., Rue, J. On the probability of planarity of a random graph near the critical point. "Proceedings of the American Mathematical Society", 01 Març 2015, vol. 143, núm. 3, p. 925-936.
Paraules clau
asymptotic enumeration, evolution, transition
Grup de recerca
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Arxius