Details of Grant 

EPSRC Reference:	EP/F008406/1
Title:	Directed graphs and the regularity method
Principal Investigator:	Kuehn, Professor D
Other Investigators:	Osthus, Professor D
Researcher Co-Investigators:
Project Partners:
Department:	School of Mathematics
Organisation:	University of Birmingham
Scheme:	Standard Research
Starts:	01 October 2007	Ends:	31 March 2011	Value (£):	118,912
EPSRC Research Topic Classifications:	Fundamentals of Computing Logic & Combinatorics
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 06 Jun 2007 Mathematics Prioritisation Panel (Science) Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.bham.ac.uk