9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details

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

Presented by Dr. Juanjo RUé
Type: Oral presentation
Track: Graph Theory


Consider the uniform random graph G(n,M) with n vertices and M edges. Erdös and Rényi (1960) conjectured that the limit lim P[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 work we determine the exact probability of a random graph being planar near the critical point M=n/2. More precisely, for each u, we find an exact analytic expression for p(u) = lim P[G(n,n/2(1+u n^{-1/3}) is planar]. In particular, we obtain that p(0) is approximately equal to 0.99780. Additionally, we are also capable to extend these results to classes of graphs closed under taking minors. This is a joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris), available on-line at http://arxiv.org/abs/1204.3376.


Location: Koper, Slovenia

Primary authors