权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Directed graphs and the regularity method

有向图和正则方法

基本信息

批准号：
EP/F008406/1
负责人：
Daniela Kuehn
金额：
$ 15.15万
依托单位：
University of Birmingham
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2007
资助国家：
英国
起止时间：
2007 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FF008406%2F1
关键词：
Directed graphs 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.

图由一组顶点组成，其中一些顶点由边连接。图形在纯数学和应用数学以及计算机科学的许多部分中自然出现。一个特别重要和困难的图论问题是，确定哪些图包含一个汉密尔顿循环（一个汉密尔顿循环是一个循环，其中包含所有顶点的图）。在无向图的情况下，这方面已经取得了一些进展。然而，有向图的几个相应的问题已经公开了几十年，我们打算使用“正则性方法”来处理这些问题。这背后的想法是，密集的大规模对象通常可以近似为具有非常简单结构的准随机对象。自1978年Szemeredi首次应用于证明整数稠密子集中任意长算术级数的存在性以来，这种方法在组合学的许多分支中取得了重大进展。然而，该方法确实有其局限性。我们对上述哈密顿性问题的研究将涉及到该方法的进一步发展。我们相信，这些将反过来导致新的应用。其中一些将被调查的一部分，拟议research.The NP-完全性的汉密尔顿循环问题意味着它是不可能的，一个有效的算法存在的问题。这也适用于提案中考虑的相关问题。因此，人们所能希望的是适用于广泛的一类（有向）图的算法。特别是，人们希望积极的结果存在的汉密尔顿周期是建设性的，即他们应该来与算法，实际上发现保证汉密尔顿周期在多项式时间。因此，我们打算采用在这方面具有建设性的办法。