Two critical behaviour of random planar graphs
- Series
- Combinatorics Seminar
- Time
- Friday, September 25, 2009 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Mihyun Kang – Technische Universitat Berlin
Since the seminal work of Erdos and Renyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. Of particular interest in recent years are random graphs with constraints (e.g. degree distribution, forbidden substructures) including random planar graphs. Let G(n,M) be a uniform random graph, a graph picked uniformly at random among all graphs on vertex set [n]={1,...,n} with M edges. Let P(n,M) be a uniform random planar graph, a graph picked uniformly at random among all graphs on vertex set [n] with M edges that are embeddable in the plane. Erodos-Renyi, Bollobas, and Janson-Knuth-Luczak-Pittel amongst others studied the critical behaviour of the largest components in G(n,M) when M= n/2+o(n) with scaling window of size n^{2/3}. For example, when M=n/2+s with s=o(n) and s \gg n^{2/3}, a.a.s. (i.e. with probability tending to 1 as n approaches \infty) G(n,M) contains a unique largest component (the giant component) of size (4+o(1))s. In contract to G(n,M) one can observe two critical behaviour in P(n,M), when M=n/2+o(n) with scaling window of size n^{2/3}, and when M=n+o(n) with scaling window of size n^{3/5}. For example, when M=n/2+s with s = o(n) and s \gg n^{2/3}, a.a.s. the largest component in P(n,M) is of size (2+o(1))s, roughly half the size of the largest component in G(n,M), whereas when M=n+t with t = o(n) and t \gg n^{3/5}, a.a.s. the number of vertices outside the giant component is \Theta(n^{3/2}t^{-3/2}). (Joint work with Tomasz Luczak)