Hamilton cycles in large graphs and hypergraphs: existence and counting

Gould, Stephen (2023). Hamilton cycles in large graphs and hypergraphs: existence and counting. University of Birmingham. Ph.D.

Preview

Gould2023PhD.pdf
Text - Accepted Version
Available under License Creative Commons Attribution.
Download (1MB) | Preview

Abstract

The study of Hamilton cycles forms a central part of classical graph theory. In this thesis we present our contribution to the modern research on this topic. In Chapter 2, we prove that \( k \)-uniform hypergraphs satisfying a `Dirac-like' condition on the minimum \( (k-1) \)-degree contain many of a natural hypergraph analogue of a Hamilton cycle. In Chapter 3, we show that almost all optimal edge-colourings of \( K_{n} \) admit a Hamilton path whose edges all have distinct colours; that is, a rainbow Hamilton path. If \( n \) is odd, we show that one is further able to find a rainbow Hamilton cycle. Chapter 4 is given to the proof that almost all optimal colourings of a directed analogue of \( K_{n} \) we call \( \overleftrightarrow{K_{n}} \) admit many rainbow directed Hamilton cycles; equivalently, almost all \( n\times n \) Latin squares contain many structures we call `Hamilton transversals'. Finally, in Chapter 5 we introduce an upcoming result which combines the R\"{o}dl Nibble with the Polynomial Method to substantially improve upon known results on the size of matchings in almost-regular hypergaphs. We also state an application of this result to the problem of finding rainbow almost-Hamilton directed cycles in any optimal colouring of \( \overleftrightarrow{K_{n}} \).

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):