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

Probabilistic Methods in Graph Theory

图论中的概率方法

基本信息

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

来源：
https://gtr.ukri.org/projects?ref=EP%2FD50564X%2F1
关键词：
Probabilistic Methods Graph Theory

项目摘要

Graph theory is a dynamic field in both theory and applications. Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices . Many problems of practical importance can be modelled using graphs: for instance a network of cities (which are represented by vertices) and connections between them give rise to weighted graph. The well known travelling salesman problem then asks for the shortest tour which visits all the cities. Similarly, one can also model scheduling problems in terms of the chromatic number of a graph (which is the smallest number of colours with which one can colour its vertices so that no adjacent vertices receive the same colour).From a theoretical point of view it is important to gain a better understanding of the relationship and the influence of the basic graph parameters like minimum degree, connectivity, girth and chromatic number. The increasing use of techniques like the probabilistic method and tools like the Regularity lemma and the Blow-up lemma has contributed to much recent progress in this field. However, I believe that their potential is far from fully explored. Roughly speaking, using the probabilistic method means that one demonstrates the existence of the desired object or configuration not constructively, but by showing that it appears with positive probability in a suitably designed probability space. While this might sound like a strange idea at first, it does provide a powerful approach, with applications ranging from theoretical computer science to number theory and analysis.The first area of the project concerns packing and embedding problems for graphs. One of the most famous results here is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle, i.e. a cycle which contains all of its vertices. Another important example is Hall's marriage theorem, which gives a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph G, i.e. a set of disjoint edges containing all vertices of G. More generally, given two graphs F and G, we say that a perfect F-packing in G is a collection of disjoint copies of F in G that cover all the vertices of G. A celebrated result of Komlos, Sarkozy and Szemeredi gives a necessary condition for the existence of a perfect F-packing in G in terms of the chromatic number of F and the minimum degree of G. However, it has recently emerged that perhaps the so-called critical chromatic number of F is the correct parameter to look at and the main aim of the first part of the project is to settle this question.The second area is concerned with extremal problems for hypergraphs. Similar packing and embedding question to the ones discussed above arise also if we consider r-uniform hypergraphs instead of graphs (so instead of edges, we now have hyperedges, each consisting of r vertices). Unfortunately, the corresponding problems turn out to be much harder to solve in the hypergraph case, so little is known so far. However, the area has been going through spectacular growth recently due to the advent of new tools like the so-called hypergraph regularity lemma. One of the aims in this part of the project is to prove an analogue of the abovementioned theorem of Dirac for r-uniform hypergraphs.The third area is concerned with minors and subdvisions in graphs and directed graphs. Minors and subdivisions may be considered as a generalization of subgraphs. They arise quite naturally, for instance planar graphs (i.e. graphs that can be embedded in the plane without crossing edges) can be charactarized by forbidden subdivisions. However, the existence of subdivisions in graphs in which every edge is directed is far from understood. One aim in the last part of the project is obtain more insight here.

图论无论在理论上还是在应用上都是一个充满活力的领域。图由一组顶点和一组连接这些顶点的边组成。许多具有实际意义的问题可以用图来建模：例如，城市网络（由顶点表示）和它们之间的连接产生了加权图。著名的旅行推销员问题，然后要求访问所有城市的最短行程。类似地，我们也可以用图的色数来建模调度问题（色数是指可以给图的顶点着色的最小颜色数，使得相邻的顶点都不具有相同的颜色）。从理论的角度来看，更好地理解图的基本参数（如最小度、连通性、围长和色数）之间的关系和影响是很重要的。越来越多地使用的技术，如概率方法和工具，如正则性引理和爆破引理，有助于在这一领域的许多最新进展。然而，我认为，它们的潜力远未得到充分开发。粗略地说，使用概率方法意味着人们不是通过建设性地证明所需对象或配置的存在，而是通过显示它在适当设计的概率空间中以正概率出现。虽然这可能听起来像一个奇怪的想法在第一，它确实提供了一个强大的方法，与应用范围从理论计算机科学数论和分析。该项目的第一个领域涉及包装和嵌入问题的图。这里最著名的结果之一是狄拉克定理，它指出每个具有n个顶点且最小度至少为n/2的图G包含一个汉密尔顿圈，即包含其所有顶点的圈。另一个重要的例子是霍尔婚姻定理，它给出了二分图G中存在完美匹配的充分必要条件，即一组包含G的所有顶点的不相交边。更一般地，给定两个图F和G，我们说G中的完美F-填充是F在G中的不相交副本的集合，这些副本覆盖G的所有顶点。Komlos，Sarkozy和Szemeredi的一个著名结果，用F的色数和G的最小度给出了G中存在完美F-填充的一个必要条件.然而，最近出现的是，也许所谓的临界色数的F是正确的参数看，该项目的第一部分的主要目的是解决这个问题。第二个领域是关于超图的极值问题。如果我们考虑r-一致超图而不是图（所以我们现在有超边，每个超边由r个顶点组成），也会出现与上面讨论的类似的填充和嵌入问题。不幸的是，在超图的情况下，相应的问题变得更加难以解决，所以到目前为止知之甚少。然而，由于新工具的出现，如所谓的超图正则性引理，该领域最近一直在经历惊人的增长。这部分的目的之一是证明r-一致超图的Dirac定理的类似定理。第三个领域是关于图和有向图中的子图和子图。子图和子图可以看作是子图的推广。它们很自然地出现，例如平面图（即可以嵌入平面而没有交叉边的图）可以通过禁止细分来表征。然而，存在的细分图中的每一个边缘是直接的是远远没有理解。项目最后部分的一个目标是在这里获得更多的洞察力。