The order of the largest complete minor in a random graph
| dc.creator | Fountoulakis, N. | |
| dc.creator | Kühn, D. | |
| dc.creator | Osthus, D. | |
| dc.date | 2007-05-02 | |
| dc.date.accessioned | 2026-07-07T07:59:09Z | |
| dc.date.available | 2026-07-07T07:59:09Z | |
| dc.description | 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 asymptotically determined ccl(G (n,p)) when p is a constant. Luczak, Pittel and Wierman gave bounds on ccl(G(n,p)) when p is very close to 1/n, i.e. inside the phase transition. Extending the results of Bollobas, Catlin and Erdos, we determine ccl(G(n,p)) quite tightly, for p>C/n where C is a large constant. If p=C/n, for an arbitrary constant C>1, then we show that asymptotically almost surely ccl(G (n,p)) is of order square-root of n. This answers a question of Krivelevich and Sudakov. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/0705.0325 | |
| dc.identifier | http://arxiv.org/abs/0705.0325 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/128262 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80, 05C83 (Primary) 60C05 (Secondary) | |
| dc.title | The order of the largest complete minor in a random graph | |
| dc.type | text |