Projects per year
Abstract
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), 195199) asymptotically determined ccl(G(n,p)) when p is a constant. Luczak, Pittel and Wierman (Trans Am Math Soc 341 (1994) 721748) 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), 195199) and answers a question of Krivelevich and Sudakov (preprint, 2006). (C) 2008 Wiley Periodicals, Inc.
Original language  English 

Pages (fromto)  127141 
Number of pages  15 
Journal  Random Structures and Algorithms 
Volume  33 
Issue number  2 
DOIs  
Publication status  Published  1 Sept 2008 
Keywords
 graph minors
 random graphs
Fingerprint
Dive into the research topics of 'The order of the largest complete minor in a random graph'. Together they form a unique fingerprint.Projects
 1 Finished

Probabilistic Methods in Graph Theory
Engineering & Physical Science Research Council
26/04/06 → 25/01/09
Project: Research Councils