Extremal graph theory via structural analysis

Garbe, Frederik (2018). Extremal graph theory via structural analysis. University of Birmingham. Ph.D.

[img]
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)EmailORCID
Mycroft, RichardUNSPECIFIEDUNSPECIFIED
Licence: All rights reserved
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/8869

Actions

Request a Correction Request a Correction
View Item View Item

Downloads

Downloads per month over past year