The order of the largest complete minor in a random graph

Let ccl(G) denote the order of the largest complete minor in a graph G (also called the contraction clique number) and let G(n,p) denote a random graph on n vertices with edge probability p. Bollobas, Catlin, and Erdos (Eur J Combin 1 (1980), 195-199) asymptotically determined ccl(G(n,p)) when p is a constant. Luczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721-748) gave bounds on ccl(G(n,p)) when p is very close to 1/n, i.e. inside the phase transition. We show that for every epsilon > 0 there exists a constant C such that whenever C/n <p <1 - epsilon then asymptotically almost surely ccl(G(n,p)) (1 +/- epsilon)n/root log(b)(np), where b := 1/(1 - p). If p = C/n for a constant C > 1, then ccl(G(n,p)) = Theta (root n). This extends the results in (Bollobas, Catlin, and P. Erdos, Ear J Combin 1 (1980), 195-199) and answers a question of Krivelevich and Sudakov (preprint, 2006). (C) 2008 Wiley Periodicals, Inc.