| EPSRC Reference: |
EP/R00532X/1 |
| Title: |
Packing and labelling large-scale graphs |
| Principal Investigator: |
Boettcher, Professor J |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
London School of Economics & Pol Sci |
| Scheme: |
First Grant - Revised 2009 |
| Starts: |
01 January 2018 |
Ends: |
31 December 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 so-called 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 long-standing 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 non-academic 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 |