Minors in random regular graphs
| dc.creator | Fountoulakis, N. | |
| dc.creator | Kühn, D. | |
| dc.creator | Osthus, D. | |
| dc.date | 2008-03-20 | |
| dc.date.accessioned | 2026-07-07T09:27:39Z | |
| dc.date.available | 2026-07-07T09:27:39Z | |
| dc.description | We show that there is a constant c>0 so that for any fixed r which is at least 3 a.a.s. an r-regular graph on n vertices contains a complete graph on c n^{1/2} vertices as a minor. This confirms a conjecture of Markstrom. Since any minor of an r-regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph G(n,p) during the phase transition (i.e. when pn is close to 1). | |
| dc.description | 18 pages | |
| dc.identifier | https://arxiv.org/abs/0803.3001 | |
| dc.identifier | http://arxiv.org/abs/0803.3001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/157181 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80 (Primary) 05C83, 60C05 (Secondary) | |
| dc.title | Minors in random regular graphs | |
| dc.type | text |