The regularity method in directed graphs and hypergraphs

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.