Abstract
dc:description.abstractWe 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.
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
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Garbe, Frederik
Subjects
dc:subject × 1Rights
- Language dc:language.dcterms_iso639_2
- eng