Directed graphs and the regularity method
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
A graph consists of a set of vertices, some of which are joined by edges. Graphs arise naturally in many parts of Pure and Applied Mathematics, as well as Computer Science. A particularly important and difficult graph theoretical problem is that of determining which graphs contain a Hamilton cycle (a Hamilton cycle is a cycle which contains all the vertices of a graph). Some progress has been made towards this in the case of undirected graphs. However, several corresponding conjectures for directed graphs have been open for decades.We intend to use the `regularity method' to approach these problems. The idea behind this is that dense large-scale objects can often be approximated by quasi-random objects with a very simple structure. Since its initial application by Szemeredi in 1978 to prove the existence of arbitrary long arithmetic progressions in dense subsets of the integers, this method has led to major advances in many branches of Combinatorics and beyond. However, the method does have its limitations. Our approaches to the above Hamiltonicity problems will involve further developments of the method. We believe that these will in turn lead to new applications. Some of these will be investigated as part of the proposed research.The NP-completeness of the Hamilton cycle problem means that it is unlikely that an efficient algorithm for the problem exists. This also applies to the related problems considered in the proposal. So all one can hope for are algorithms which work for a wide class of (directed) graphs. In particular, one would like positive results on the existence of Hamilton cycles to be constructive, i.e. they should come with an algorithm which actually finds the guaranteed Hamilton cycle in polynomial time. Accordingly, we intend to use approaches which are constructive in this sense.
Organisations
People |
ORCID iD |
Daniela Kuehn (Principal Investigator) | |
Deryk Osthus (Co-Investigator) |
Publications
Christofides D
(2010)
A Semiexact Degree Condition for Hamilton Cycles in Digraphs
in SIAM Journal on Discrete Mathematics
Keevash P
(2009)
An exact minimum degree condition for Hamilton cycles in oriented graphs
in Journal of the London Mathematical Society
KELLY L
(2008)
A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
in Combinatorics, Probability and Computing
Kelly L
(2010)
Cycles of given length in oriented graphs
in Journal of Combinatorial Theory, Series B
Knox F
(2011)
Approximate Hamilton decompositions of random graphs
in Random Structures & Algorithms
Knox F
(2015)
Edge-disjoint Hamilton cycles in random graphs
in Random Structures & Algorithms
Kühn D
(2009)
An Ore-type Theorem for Perfect Packings in Graphs
in SIAM Journal on Discrete Mathematics
Kühn D
(2011)
A proof of Sumner's universal tournament conjecture for large tournaments
in Proceedings of the London Mathematical Society
Kühn D
(2008)
k-Ordered Hamilton cycles in digraphs
in Journal of Combinatorial Theory, Series B
Kühn D
(2010)
Hamilton decompositions of regular tournaments
in Proceedings of the London Mathematical Society
Description | A graph consists of a set of vertices, some of which are joined by edges. Graphs arise naturally in many parts of Pure and Applied Mathematics, as well as Computer Science. A particularly important and difficult graph theoretical problem is that of determining which graphs contain a Hamilton cycle (a Hamilton cycle is a cycle which contains all the vertices of a graph). Some progress has been made towards this in the case of undirected graphs. However, several corresponding conjectures for directed graphs have been open for decades. In the project, we used the `regularity method' to approach some of these problems.The idea behind this is that dense large-scale objects can often be approximated by quasi-random objects with a very simple structure. Since its initial application by Szemeredi in 1978 to prove the existence of arbitrary long arithmetic progressions in dense subsets of the integers, this method has led to major advances in many branches of Combinatorics and beyond. Our approaches to the above Hamiltonicity problems involved further developments of the method. We believe that these will in turn lead to new applications. The NP-completeness of the Hamilton cycle problem means that it is unlikely that an efficient algorithm for the problem exists. This also applies to the related problems considered in the proposal. So all one can hope for are algorithms which work for a wide class of (directed) graphs. In particular, one would like positive results on the existence of Hamilton cycles to be constructive, i.e. they should come with an algorithm which actually finds the guaranteed Hamilton cycle in polynomial time. Accordingly, in many parts of the project we used approaches which are constructive in this sense. |
Exploitation Route | The methods developed to prove the objectives in the proposal have found applications to related problems in the field, including advances on several longstanding problems (for example Kelly's conjecture on Hamilton decompositions). |
Sectors | Digital/Communication/Information Technologies (including Software) |
URL | http://web.mat.bham.ac.uk/D.Kuehn/pubdk.html |
Description | Some of the results obtained in the project have settled conjectures which had been open for several decades (for example Sumner's universal tournament conjecture). Moreover, both the results proved in this project as well as the methods developed for these proofs have also found further applications and have led to significant advances on related problems (e.g. the proof of Kelly's conjecture on Hamilton decompositions). |