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

Graph expansion and applications

图扩展及应用

基本信息

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

来源：
https://gtr.ukri.org/projects?ref=EP%2FE02162X%2F1
关键词：
Graph expansion applications

项目摘要

The proposed research falls into the area of Graph theory. Graphs consist of a set of vertices which are connected by edges and can be used to model many kinds of problems. The project will focus on the class of expanding graphs. These arise in several areas of both Pure Mathematics and Theoretical Computer Science. A graph is called expanding if for every set of its vertices, the set of its neighbours of is comparatively large. Intuitively, this means that such a graph contains no `bottlenecks': it is not possible to cut the graph into several large pieces by removing only a few vertices. Expansion can be characterized in many different ways. For example, one way of thinking about expansion is in terms of random graphs: random graphs enjoy very strong expansion properties (with high probability). Conversely, if a graph is expanding, this usually makes it behave like a random graph (in a well-defined sense). A simple example of this is that the average distance between pairs of vertices is comparatively small.Expansion is a property that links many different areas together. The area where expanding graphs first explicitly arose was complexity theory (where for example they were used as building blocks to `amplify' the properties of some given construction and were used in the construction of efficient sorting networks). Another example is that random walks on expanding graphs yield rapidly mixing Markov chains (i.e. they quickly `forget' where they started from). This has important applications in Combinatorial Optimization and Statistical Physics. For instance it allows one to sample certain configurations efficiently and almost uniformly at random.However, we are still a long way from a satisfactory understanding of the way expansion forces useful combinatorial properties and, conversely, how one can prove that some graph is expanding. Motivated by this, the first aim of this project is to investigate the influence of expansion on Hamilton cycles in graphs. A Hamilton cycle is a cycle containing all the vertices of the graph. The question of which graphs contain a Hamilton cycle is a fundamental problem in Combinatorial Optimization and Theoretical Computer Science. There are several open questions in the area which I believe can be approached in a unified way (using techniques based on expansion of the underlying graph).The second aim is to investigate expansion of graphs of 0/1 polytopes. This is an important class of graphs arising in Combinatorial Optimization whose structural properties are not well understood.The third aim is to investigate properties of scale-free random graphs, in particular those related to their expansion. These graphs are used for example as models for the structure of the internet.

拟议的研究属于图论领域。图由一组通过边连接的顶点组成，可用于对多种问题进行建模。该项目将重点关注扩展图类。这些出现在纯数学和理论计算机科学的多个领域。如果对于图的每组顶点，其邻居的集合都相对较大，则该图被称为扩展图。直观上，这意味着这样的图不包含“瓶颈”：不可能通过仅删除几个顶点来将图切割成几个大块。扩张可以用许多不同的方式来表征。例如，考虑扩展的一种方式是使用随机图：随机图具有非常强的扩展特性（概率很高）。相反，如果图正在扩展，这通常会使其表现得像随机图（在明确定义的意义上）。一个简单的例子是顶点对之间的平均距离相对较小。扩展是将许多不同区域连接在一起的属性。扩展图首先明确出现的领域是复杂性理论（例如，它们被用作构建块来“放大”某些给定结构的属性，并用于构建高效的排序网络）。另一个例子是，扩展图上的随机游走会产生快速混合的马尔可夫链（即它们很快“忘记”它们从哪里开始）。这在组合优化和统计物理中具有重要的应用。例如，它允许人们有效地、几乎均匀地随机地对某些配置进行采样。然而，我们距离令人满意地理解扩展如何强制有用的组合属性以及相反地如何证明某个图正在扩展还有很长的路要走。受此启发，该项目的首要目标是研究展开对图中汉密尔顿循环的影响。汉密尔顿循环是包含图的所有顶点的循环。哪些图包含哈密尔顿循环的问题是组合优化和理论计算机科学中的一个基本问题。我相信该领域有几个悬而未决的问题，可以通过统一的方式来解决（使用基于底层图扩展的技术）。第二个目标是研究 0/1 多胞体图的扩展。这是组合优化中出现的一类重要的图，其结构特性尚未得到很好的理解。第三个目标是研究无标度随机图的特性，特别是与其扩展相关的特性。例如，这些图被用作互联网结构的模型。