Directed graphs and the regularity method

点击翻译按钮获取中文摘要

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.