Directed graphs and the regularity method

图由一组顶点组成，其中一些顶点由边连接。图自然地出现在纯数学和应用数学的许多部分，以及计算机科学。一个特别重要和困难的图理论问题是确定哪些图包含汉密尔顿环（汉密尔顿环是包含图中所有顶点的环）。在无向图的情况下，这方面已经取得了一些进展。然而，有向图的几个相应的猜想已经开放了几十年。我们打算用“正则性方法”来解决这些问题。这背后的想法是，密集的大尺度物体通常可以用具有非常简单结构的准随机物体来近似。自从1978年Szemeredi首次应用该方法来证明整数密集子集中任意长等分数列的存在性以来，该方法已经在组合学的许多分支以及其他领域取得了重大进展。然而，这种方法也有其局限性。我们对上述哈密顿性问题的处理将涉及该方法的进一步发展。我们相信这些将会带来新的应用。其中一些将作为拟议研究的一部分进行调查。Hamilton环问题的np完备性意味着不可能存在求解该问题的有效算法。这也适用于提案中所审议的有关问题。因此，我们所能期望的是能够适用于广泛的（有向）图的算法。特别是，人们希望关于汉密尔顿环存在性的正结果是建设性的，也就是说，他们应该有一个算法，实际上在多项式时间内找到保证的汉密尔顿环。因此，我们打算采用在这一意义上具有建设性的办法。

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.