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

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

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

Content

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.

Place

Location: Koper, Slovenia

Primary authors

More

Co-authors

More