# Robust expansion and hamiltonicity

Staden, Katherine (2015). Robust expansion and hamiltonicity. University of Birmingham. Ph.D.

 Preview
PDF - Accepted Version

## Abstract

This thesis contains four results in extremal graph theory relating to the recent notion of robust expansion, and the classical notion of Hamiltonicity. In Chapter 2 we prove that every sufficiently large ‘robustly expanding’ digraph which is dense and regular has an approximate Hamilton decomposition. This provides a common generalisation of several previous results and in turn was a crucial tool in Kühn and Osthus’s proof that in fact these conditions guarantee a Hamilton decomposition, thereby proving a conjecture of Kelly from 1968 on regular tournaments.
In Chapters 3 and 4, we prove that every sufficiently large 3-connected $$D$$-regular graph on $$n$$ vertices with $$D$$ ≥ n/4 contains a Hamilton cycle. This answers a problem of Bollobás and Häggkvist from the 1970s. Along the way, we prove a general result about the structure of dense regular graphs, and consider other applications of this.
Chapter 5 is devoted to a degree sequence analogue of the famous Pósa conjecture. Our main result is the following: if the $$i$$$$^{th}$$ largest degree in a sufficiently large graph $$G$$ on n vertices is at least a little larger than $$n$$/3 + $$i$$ for $$i$$ ≤ $$n$$/3, then $$G$$ contains the square of a Hamilton cycle.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Supervisor(s):
Supervisor(s)EmailORCID
Osthus, DerykUNSPECIFIEDUNSPECIFIED
Kuehn, DanielaUNSPECIFIEDUNSPECIFIED
Licence:
College/Faculty: Colleges (2008 onwards) > College of Engineering & Physical Sciences
School or Department: School of Mathematics
Funders: None/not applicable
Subjects: Q Science > QA Mathematics
URI: http://etheses.bham.ac.uk/id/eprint/5981

### Actions

 Request a Correction View Item