The order of the largest complete minor in a random graph
Research output: Contribution to journal › Article
Colleges, School and Institutes
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.
|Number of pages||15|
|Journal||Random Structures and Algorithms|
|Publication status||Published - 1 Sep 2008|
- graph minors, random graphs