EPSRC Reference: 
EP/E02162X/1 
Title: 
Graph expansion and applications 
Principal Investigator: 
Osthus, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
First Grant Scheme 
Starts: 
01 August 2007 
Ends: 
30 November 2009 
Value (£): 
177,840

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
08 Sep 2006

Mathematics Prioritisation Panel (Science)

Deferred


Summary on Grant Application Form 
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 welldefined 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 scalefree random graphs, in particular those related to their expansion. These graphs are used for example as models for the structure of the internet.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.bham.ac.uk 