Graph expansion and 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.