The order of the largest complete minor in a random graph |
| |
Authors: | Nikolaos Fountoulakis Daniela Kühn Deryk Osthus |
| |
Institution: | School of Mathematics, University of Birmingham, Edgbaston, Birmingham B15 2TT, UK |
| |
Abstract: | Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let Gn,p denote a random graph on n vertices with edge probability p. Bollobás, Catlin, and Erd?s (Eur J Combin 1 (1980), 195–199) asymptotically determined ccl(Gn,p) when p is a constant. ?uczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721–748) gave bounds on ccl(Gn,p) when p is very close to 1/n, i.e. inside the phase transition. We show that for every ε > 0 there exists a constant C such that whenever C/n < p < 1 ‐ ε then asymptotically almost surely ccl(Gn,p) = (1 ± ε)n/ , where b := 1/(1 ‐ p). If p = C/n for a constant C > 1, then ccl(Gn,p) = Θ( ). This extends the results in (Bollobás, Catlin, and P. Erd?s, Eur J Combin 1 (1980), 195–199) and answers a question of Krivelevich and Sudakov (preprint, 2006). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
Keywords: | graph minors random graphs |
|
|