EPSRC Reference: 
EP/D50564X/1 
Title: 
Probabilistic Methods in Graph Theory 
Principal Investigator: 
Kuehn, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
First Grant Scheme PreFEC 
Starts: 
26 April 2006 
Ends: 
25 January 2009 
Value (£): 
126,249

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Graph theory is a dynamic field in both theory and applications. Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices . Many problems of practical importance can be modelled using graphs: for instance a network of cities (which are represented by vertices) and connections between them give rise to weighted graph. The well known travelling salesman problem then asks for the shortest tour which visits all the cities. Similarly, one can also model scheduling problems in terms of the chromatic number of a graph (which is the smallest number of colours with which one can colour its vertices so that no adjacent vertices receive the same colour).From a theoretical point of view it is important to gain a better understanding of the relationship and the influence of the basic graph parameters like minimum degree, connectivity, girth and chromatic number. The increasing use of techniques like the probabilistic method and tools like the Regularity lemma and the Blowup lemma has contributed to much recent progress in this field. However, I believe that their potential is far from fully explored. Roughly speaking, using the probabilistic method means that one demonstrates the existence of the desired object or configuration not constructively, but by showing that it appears with positive probability in a suitably designed probability space. While this might sound like a strange idea at first, it does provide a powerful approach, with applications ranging from theoretical computer science to number theory and analysis.The first area of the project concerns packing and embedding problems for graphs. One of the most famous results here is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle, i.e. a cycle which contains all of its vertices. Another important example is Hall's marriage theorem, which gives a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph G, i.e. a set of disjoint edges containing all vertices of G. More generally, given two graphs F and G, we say that a perfect Fpacking in G is a collection of disjoint copies of F in G that cover all the vertices of G. A celebrated result of Komlos, Sarkozy and Szemeredi gives a necessary condition for the existence of a perfect Fpacking in G in terms of the chromatic number of F and the minimum degree of G. However, it has recently emerged that perhaps the socalled critical chromatic number of F is the correct parameter to look at and the main aim of the first part of the project is to settle this question.The second area is concerned with extremal problems for hypergraphs. Similar packing and embedding question to the ones discussed above arise also if we consider runiform hypergraphs instead of graphs (so instead of edges, we now have hyperedges, each consisting of r vertices). Unfortunately, the corresponding problems turn out to be much harder to solve in the hypergraph case, so little is known so far. However, the area has been going through spectacular growth recently due to the advent of new tools like the socalled hypergraph regularity lemma. One of the aims in this part of the project is to prove an analogue of the abovementioned theorem of Dirac for runiform hypergraphs.The third area is concerned with minors and subdvisions in graphs and directed graphs. Minors and subdivisions may be considered as a generalization of subgraphs. They arise quite naturally, for instance planar graphs (i.e. graphs that can be embedded in the plane without crossing edges) can be charactarized by forbidden subdivisions. However, the existence of subdivisions in graphs in which every edge is directed is far from understood. One aim in the last part of the project is obtain more insight here.

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 