Extremal problems on graphs, directed graphs and hypergraphs

Townsend, Timothy Duncan (2016). Extremal problems on graphs, directed graphs and hypergraphs. University of Birmingham. Ph.D.

PDF - Accepted Version

Download (1MB)


This thesis is concerned with extremal problems on graphs and similar structures.
We first study degree conditions in uniform hypergraphs that force matchings of various sizes. Our main result in this area improves bounds of Markstrom and Rucinski on the minimum d-degree which forces a perfect matching in a k-uniform hypergraph on n vertices.
We then study connectivity conditions in tournaments that ensure the existence of partitions of the vertex set that satisfy various properties. In 1982 Thomassen asked whether every sufficiently strongly connected tournament T admits a partition of its vertex set into t vertex classes such that the subtournament induced on T by each class is strongly k-connected. Our main result in this area implies an affirmative answer to this question.
Finally we investigate the typical structure of graphs and directed graphs with some forbidden subgraphs. We answer a question of Cherlin by finding the typical structure of triangle-free oriented graphs. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply to digraphs.
We also determine, for all k>5, the typical structure of graphs that do not contain an induced 2k-cycle. This verifies a conjecture of Balogh and Butterfield.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
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/6453


Request a Correction Request a Correction
View Item View Item


Downloads per month over past year