eTheses Repository

The regularity method in directed graphs and hypergraphs

Mycroft, Richard (2010)
Ph.D. thesis, University of Birmingham.

Loading
PDF (1299Kb)

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:Ph.D. thesis.
Supervisor(s):Kuhn, Daniela and Osthus, Deryk
School/Faculty:Colleges (2008 onwards) > College of Engineering & Physical Sciences
Department:School of Mathematics
Subjects:QA Mathematics
Institution:University of Birmingham
ID Code:1036
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page