Embedding problems in graphs and hypergraphs

Treglown, Andrew Clark (2011). Embedding problems in graphs and hypergraphs. University of Birmingham. Ph.D.

[img]
Preview
Treglown11PhD.pdf
PDF

Download (1MB)

Abstract

The first part of this thesis concerns perfect matchings and their generalisations. We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph, thereby answering a question of Hàn, Person and Schacht. We say that a graph \(G\) has a perfect \(H\)-packing (also called an \(H\) - factor) if there exists a set of disjoint copies of \(H\) in \(G\) which together cover all the vertices of \(G\). Given a graph \(H\), we determine, asymptotically, the Ore-type degree condition which ensures that a graph \(G\) has a perfect \(H\)-packing. The second part of the thesis concerns Hamilton cycles in directed graphs. We give a condition on the degree sequences of a digraph \(G\) that ensures \(G\) is Hamiltonian. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chvatal's theorem. We also show that every sufficiently large regular tournament can almost completely be decomposed into edge-disjoint Hamilton cycles. More precisely, for each \(\eta\) >0 every regular tournament \(G\) of sufficiently large order n contains at least (1/2- \(\eta\))n edge-disjoint Hamilton cycles. This gives an approximate solution to a conjecture of Kelly from 1968.

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/1345

Actions

Request a Correction Request a Correction
View Item View Item

Downloads

Downloads per month over past year