Garbe, Frederik (2018). Extremal graph theory via structural analysis. University of Birmingham. Ph.D.
Preview |
Garbe18PhD.pdf
Text - Accepted Version Available under License All rights reserved. Download (892kB) | Preview |
Abstract
We discuss two extremal problems in extremal graph theory. First we establish a precise characterisation of 4-uniform hypergraphs with minimum codegree close to n/2 which contain a Hamilton 2-cycle. As a corollary we determine the exact Dirac threshold for Hamilton 2-cycles in 4-uniform hypergraphs, and we provide a polynomial-time algorithm which answers the corresponding decision problem for 4-graphs with minimum degree close to n/2. In contrast we also show that the corresponding decision problem for tight Hamilton cycles in dense k-graphs is NP-complete.
Furthermore we study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a p-proportion of its neighbours are infected. A set A which infects the whole graph is called a contagious set.
Our main result states that for every pin (0,1] and for every connected graph G on n vertices the minimal size of a contagious set is less than 2pn or 1. This result is best-possible, but we provide a stronger bound in the case of graphs of girth at least five. Both proofs exploit the structure of a minimal counterexample.
| Type of Work: | Thesis (Doctorates > Ph.D.) |
|---|---|
| Award Type: | Doctorates > Ph.D. |
| Supervisor(s): | Supervisor(s) Email ORCID Mycroft, Richard UNSPECIFIED UNSPECIFIED |
| Licence: | All rights reserved |
| College/Faculty: | Colleges > College of Engineering & Physical Sciences |
| School or Department: | School of Mathematics |
| Funders: | None/not applicable |
| Subjects: | Q Science > QA Mathematics |
| URI: | https://bham-theses.eprints-hosting.org/id/eprint/8869 |
Actions
![]() |
Request a Correction |
![]() |
View Item |
Downloads
Downloads per month over past year
Tools
Tools
