The regularity method in directed graphs and hypergraphs

Mycroft, Richard (2010). The regularity method in directed graphs and hypergraphs. University of Birmingham. Ph.D.

[img]
Preview
Mycroft10PhD.pdf
PDF

Download (1MB)

Abstract

In recent years the regularity method has been used to tackle many embedding problems in extremal graph theory. This thesis demonstrates and develops three different techniques which can be used in conjunction with the regularity method to solve such problems. These methods enable us to prove an approximate version of the well-known Sumner’s universal tournament conjecture, first posed in 1971, which states that any tournament G on 2n − 2 vertices contains a copy of any directed tree T on n vertices. An analysis of the extremal cases then proves that Sumner’s universal tournament conjecture holds for any sufficiently large n. Our methods are also applied to the problem of obtaining hypergraph analogues of Dirac’s theorem. Indeed, we show that for any k \(\geqslant\) 3 and any 1 \(\leqslant\) \(\ell\) \(\leqslant\) k − 1 with k - \(\ell\)\(\nmid\)k, any k-uniform hypergraph on n vertices with minimum degree at least \(\frac{n}{\lceil k / (k - \ell) \rceil (k - \ell)}\) + o(n) contains a Hamilton \(\ell\)-cycle. This result confirms a conjecture of Han and Schacht, and is best possible up to the o(n) error term. Together with results of Rodl, Rucinski and Szemeredi, this result asymptotically determines the minimum degree which forces an \(\ell\)-cycle for any \(\ell\) with 1 \(\leqslant\)\(\ell\)\(\leqslant\) k − 1.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Supervisor(s):
Supervisor(s)EmailORCID
Kuhn, DanielaUNSPECIFIEDUNSPECIFIED
Osthus, DerykUNSPECIFIEDUNSPECIFIED
Licence:
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/1036

Actions

Request a Correction Request a Correction
View Item View Item

Downloads

Downloads per month over past year