University of Birmingham
Hamilton cycles in large graphs and hypergraphs: existence and counting
Abstract
dc:description.abstractThe 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 Kn 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 Kn we call \overleftrightarrow{Kn} 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{Kn} .
Degree
thesis:*- Name dc:type.qualificationname
- d_ph
- Level dc:type.qualificationlevel
- d_ph
- Grantor dc:publisher.institution
- University of Birmingham
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gould, Stephen
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng