University of Oxford
Mathematical Institute

The study of graphs started during the 18th century with the seminal paper of Euler on the Seven Bridges of Königsberg. A graph is a pure mathematical object that is also used to model complex systems and processes. Graphs have a tremendous amount of applications in different fields such as networks, algorithms, physics, life sciences, and more. A graph consists of a set of vertices and a set of pairs of vertices, the edges, representing connections between the vertices. For studying more complicated systems, we consider hypergraphs, where we allow edges of different sizes and not just pairs. The study of complicated networks motivates the following important question: under which conditions can a (hyper)graph be decomposed into simpler sub(hyper)graphs of prescribed form?

The area of (hyper)graph decomposition has a long history and can be tracked back to the famous Kirkman’s schoolgirl problem from 1850. The goal in these type of problems is to split the (hyper)graph into pieces all having a prescribed structure. This notion is strongly connected to edge colouring, where we identify each colour class with a sub(hyper)graph of the decomposition. In the most basic form, the colouring problem asks for the minimum number of colours needed in order to split the edges of the (hyper)graph into matchings (where a matching is a disjoint collection of edges). These types of problems are known to be especially difficult in the context of hypergraphs.

While matchings are the simplest subgraphs to consider, in many cases the goal is to partition the graph into fewer colour classes, each having a desired form. In this proposal, we focus on natural generalisations of matchings, such as splitting the graph into linear forests (collections of disjoint paths), and into collections of disjoint triangles (or more generally, cliques). We study the above concepts also in the random setting, that is, consider graphs and hypergraphs sampled from a collection of graphs according to some probability distribution.

This ambitious project generalises classical problems in graph theory, and will greatly advance the field by bringing together concepts and techniques from probability, structural, and extremal graph theory.