Packing and labelling large-scale graphs

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.

The questions studied in Combinatorial Packing, the subject area of the proposed research, have a variety of applications for example in Biology, Statistics, Sociology, and Information Theory. These applications include, among many others, the mathematical underpinnings of the design of experiments in Statistics, the design of error correcting codes important for telecommunication, and problems concerning the organisation of data in a computer.

The mentioned applications are influential in economy and society. Impact of the proposed research on these applications will, however, be necessarily indirect and long-term, due to limits in the methods available at the moment. A better understanding of the problems at hand, which is a main goal of the proposed research, though is likely eventually to lead to refined methods which are closer to these applications.

The impact I expect to be generated during the time frame of this project concentrates on the dissemination of knowledge and skills in the field, and on the building of research capacity by training and influencing young researchers.

In particular, the project is well suited to introducing PhD students in the field to influential modern methods and expose them to important research problems which receive national and international attention. The proposed work includes aims at the right level for PhD research. Training PhD students in Combinatorics is of importance for public and private employers in fields such as computing, communication technology, and information security.

The proposed methods and approaches further have fundamental ties to problems pursued in Computer Science and Probability Theory. They thus provide the potential to strengthen existing links between Combinatorics and these areas. I expect such strengthened links to be beneficial for researchers of each of these three areas, providing the basis for discovering new viewpoints on existing problems as well as stimulating new questions and the development of new techniques.

Moreover, Combinatorial Packing has the virtue of featuring a number of research problems that are easy to phrase and visualise, without requiring much mathematical background. They can often even be exemplified as mathematical puzzles understandable to secondary school pupils. Therefore the presentation of problems and results from the proposed area of research is well suited for reaching and motivating the next generation of students in Mathematics. This is of importance particularly in the sectors of Banking and Finance, Computer Services, and the Pharmaceutical Industry. I will contribute to the promotion of studies in Mathematics in cooperation with secondary schools, using the topic of the proposed research and its fascinating background as a basis.