Graph expansion and applications
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
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.
Organisations
People |
ORCID iD |
Deryk Osthus (Principal Investigator) |
Publications
Christofides D
(2012)
Edge-disjoint Hamilton cycles in graphs
in Journal of Combinatorial Theory, Series B
Christofides D
(2010)
Influences of monotone Boolean functions
in Discrete Mathematics
Christofides D
(2007)
Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
in Random Structures & Algorithms
Christofides D
(2010)
A semi-exact degree condition for Hamilton cycles in digraphs
Christofides D
(2012)
Finding Hamilton cycles in robustly expanding digraphs
in Journal of Graph Algorithms and Applications
Christofides D
(2010)
A Semiexact Degree Condition for Hamilton Cycles in Digraphs
in SIAM Journal on Discrete Mathematics
Keevash P
(2011)
Loose Hamilton cycles in hypergraphs
in Discrete Mathematics
Keevash P
(2009)
An exact minimum degree condition for Hamilton cycles in oriented graphs
in Journal of the London Mathematical Society
Kelly L
(2007)
A Dirac type result on Hamilton cycles in oriented graphs
Description | 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, a major aim of this project is to investigate the influence of expansion on Hamiltonicity. 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). |
Exploitation Route | The techniques used by several teams of researchers to further develop the area. |
Sectors | Digital/Communication/Information Technologies (including Software) |
URL | http://web.mat.bham.ac.uk/D.Osthus/pubdo.html |
Description | The methods have been used to prove several long-standing conjectures in the area. The also have applications to other areas of research, e.g. Theoretical Computer Science and Algorithms |
First Year Of Impact | 2010 |
Sector | Digital/Communication/Information Technologies (including Software) |
Impact Types | Economic |