Projects per year
Abstract
In this paper, we study the large-scale structure of dense regular graphs. This involves the notion of robust expansion, a recent concept which has already been used successfully to settle several longstanding problems. Roughly speaking, a graph is robustly expanding if it still expands after the deletion of a small fraction of its vertices and edges. Our main result allows us to harness the useful consequences of robust expansion even if the graph itself is not a robust expander. It states that every dense regular graph can be partitioned into ‘robust components’, each of which is a robust expander or a bipartite robust expander. We apply our result to obtain (amongst others) the following.
We prove that whenever ε>0, every sufficiently large 3-connected D-regular graph on n vertices with D≥(14+ε)n is Hamiltonian. This asymptotically confirms the only remaining case of a conjecture raised independently by Bollobás and Häggkvist in the 1970s.
We prove an asymptotically best possible result on the circumference of dense regular graphs of given connectivity. The 2-connected case of this was conjectured by Bondy and proved by Wei.
Original language | English |
---|---|
Pages (from-to) | 19-56 |
Number of pages | 38 |
Journal | London Mathematical Society. Proceedings |
Volume | 110 |
Issue number | 1 |
Early online date | 20 Oct 2014 |
DOIs | |
Publication status | Published - 1 Jan 2015 |
Fingerprint
Dive into the research topics of 'The robust component structure of dense regular graphs and applications'. Together they form a unique fingerprint.Projects
- 1 Finished
-
FP7- ERC - QRGraph: Quasirandomness in Graphs and Hypergraphs
European Commission, European Commission - Management Costs
1/12/10 → 30/11/15
Project: Research