Dr Katherine Staden

Graphs, or networks, are abstract mathematical objects ubiquitous in modern life, from social network Instagram, the London Underground transport network, neural networks in artificial intelligence, to disease networks used to model epidemics. Beneath them all are a common object: a graph — a collection of points (vertices) some of which are joined by lines (edges) — for example, each point represents a station and if there is a train line between them, we draw a line. To decide whether it is possible to visit every station exactly once and return to the starting station, the underlying graph captures all the information that is needed, and what we seek is a structure inside the graph called a Hamilton cycle. Mathematical tools from the combinatorial field of graph theory — the study of networks — can now be brought to bear. Efficient algorithms for problems such as these are of particular importance: Google's PageRank algorithm used by its search engine assigns scores to webpages by analysing the underlying graph; while ChatGPT's brain is a knowledge graph capturing the relationships between a huge quantity of data points. Many graph theoretic problems are NP-complete, meaning that it is unlikely a fast algorithm — in relation to the size of the network — exists. Hence, for the huge networks that are employed today, it is of great interest to obtain sufficient conditions that guarantee a particular property and to understand the worst-case — or extremal — behaviour of graphs. This is the realm of extremal graph theory. Mathematicians have been studying graphs and related combinatorial objects for centuries. This study has led to numerous applications of which I only offer a glimpse above. Much of this research has been driven by the pursuit of understanding the most fundamental properties of graphs and their structure. My proposed research has two ambitious strands, each investigating different fundamental properties of graphs related to structures within them. The first strand addresses counting structures in graphs and related objects and the extremal problem of maximising or minimising this count. This question is at the very heart of extremal combinatorics and has driven several of the key developments in the field such as flag algebras and the use of computers to produce mathematical proofs. I will investigate new and old problems of this type, focusing on the intriguing connections between seemingly unrelated problems that have been hinted at in previous work. The second strand is about graph decomposition which is the problem of partitioning a graph into given pieces, such as Hamilton cycles. Whether this can be achieved is an old problem going all the way back to Euler, while today decompositions have applications in the design of statistical experiments. I will address some of the unsolved theoretical questions concerning decomposition, building upon my previous advances in this area.

The notion of decomposition, or splitting a larger object into smaller pieces, is ubiquitous in mathematics. Sometimes one does this to better understand the larger object, for example representing a function by a Fourier series, or factorising an integer. On the other hand, we may wish to understand which pieces can possibly partition a given larger object. With which shapes can we tile the plane? Is it possible to 'decompose' the computationally expensive operation of division into only addition, subtraction and multiplication (as in an algorithm used by a computer to divide real numbers)? This proposal seeks to investigate these problems in graphs, or networks. A graph is a collection of nodes in which some pairs are joined by edges, to represent some relationship or connection between them. More complicated relationships are encoded by hypergraphs, where more than two nodes can lie in an edge together. Graphs are used to model and describe many different systems in biology, communications and computer science and their theoretical study comes under the mathematical field of combinatorics. In the graph setting, the goal of a decomposition problem is to start with a large 'host' graph with many edges, and a collection of 'guest' graphs each with few edges, and to try to fit the guest graphs perfectly into the host graph, using each edge exactly once. This type of problem is one of the oldest in combinatorics, going back to a 1792 question of Euler. The case where each guest graph contains few nodes is by now fairly well-understood and constitutes the area of design theory. This project investigates the other end of the spectrum where guest graphs may contain a number of nodes comparable with the host graph. An example of such a question that can be expressed in the language of graphs, the recently solved Oberwolfach problem, asks for a sequence of seating plans which allow each person in a group to sit next to each other person exactly once over the course of several meals. Very recent successes in this area, including work in which I was involved, solved a number of longstanding conjectures and overcame the barriers met in previous works by novel application of tools from disciplines outside of combinatorics. I seek to build on these successes and draw from tools in probability and design theory to obtain graph decompositions. For example, an effective strategy has been to use a randomised algorithm that makes successive coin flips to choose where to put each guest edge; tools from probability are needed to analyse its evolution. Such an algorithm is very unlikely to be able to place the final pieces correctly; tools from design theory will help complete the decomposition.