EPSRC Reference: 
EP/R00532X/1 
Title: 
Packing and labelling largescale graphs 
Principal Investigator: 
Boettcher, Dr J 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
London School of Economics & Pol Sci 
Scheme: 
First Grant  Revised 2009 
Starts: 
01 October 2017 
Ends: 
30 September 2019 
Value (£): 
97,801

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
Financial Services 
Pharmaceuticals and Biotechnology 
Information Technologies 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
The investigation of combinatorial packing problems, which is the main topic of the proposed research, is basic mathematical research. The objects under study in this field, graphs and hypergraphs, serve as a model for networks, the study of which has drastically increased in importance with the omnipresence in modern life of digital computing and communication technology. Logistical networks, road networks, communication networks and social networks are all examples of graphs that appear in practice. Graphs are also the mathematical structures underlying the study of vehicle navigation problems, the spread of epidemic diseases, the modelling of neural networks, and the analysis of large sets of data. It is therefore important that we develop a sound understanding of the fundamental properties of graphs and hypergraphs, and can predict how certain structural phenomena influence their overall behaviour. The proposed research aims at contributing significantly to this understanding.
A graph consists of vertices representing certain entities, and edges representing connections or relations between two of these entities. A hypergraph extends this concept to situations where relations between more than two entities are possible. Graph packing problems then ask when several graphs can be made "compatible" in the following sense: We want to arrange the different graphs such that they all use the same vertex set, but do not overlap in any edges. Problems of this type have applications in such diverse areas as the theory of algorithms, the theory of information, in experiment design in statistics, in computational biology, and the theory of games.
Graph and hypergraph packing problems have a long and exciting history. The area has seen several recent breakthroughs. One of the oldest and most fundamental topics in the area concerns socalled combinatorial designs, in turn a serious and important generalisation of a problem posed famously by Kirkman in 1850 and now known as the "Kirkman schoolgirl problem". It came as a spectacular surprise when Keevash recently resolved the longstanding question of establishing the existence of such combinatorial designs under certain natural conditions.
The proposed research focuses on related questions concerning the packing of different, larger structures. Although problems of this type have been studied for a number of decades already, there has been a significant increase in attention recently. Two famous examples of such problems are the unsolved packing conjectures for trees by Ringel from 1963 and by Gyárfás from 1973. A related concept, which in disguise asks for the existence of particularly symmetric packings of trees, is that of a graceful labelling of a tree. Many extensions of these questions were considered. Though much studied, these problems remained poorly understood for a long time, with no significant progress until recently. But in the last few years novel approaches using modern tools from Probabilistic and Extremal Combinatorics led to important advances, in some of which I was involved.
The aim of this project is to enhance these approaches and results with new techniques in order to gain a better understanding of graph packing and graceful labelling problems in general. The goal is that this will improve the set of tools available for obtaining such packings and labellings, allow me to establish packing results for much more general classes of graphs than known at the moment, and to approach the mentioned key conjectures in more generality. Simple processes crucially relying on the use of randomness and on modern tools from the area of Probability Theory will form a key component of these new techniques.

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.lse.ac.uk 