Graph expansion and applications

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

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.