# The order of the largest complete minor in a random graph

Research output: Contribution to journal › Article

## Authors

## Colleges, School and Institutes

## 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), 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.

## Details

Original language | English |
---|---|

Pages (from-to) | 127-141 |

Number of pages | 15 |

Journal | Random Structures and Algorithms |

Volume | 33 |

Issue number | 2 |

Publication status | Published - 1 Sep 2008 |

## Keywords

- graph minors, random graphs