Saturation problems on Graphs and Other Combinatorial Structures

A graph is a discrete mathematical structure consisting of a set of points (called vertices) some pairs of which are linked by edges. Extremal graph theory is concerned with which global parameters of a graph (such as the number of edges) force the graph to have certain structure. A classic example is Mantel's theorem which determines the maximum number of edges that a graph on n vertices without a triangle (three linked vertices) can have. Mantel's Theorem is the starting point for a well-developed theory of Turan-type extremal problems. These are concerned with determining the maximum number of edges a graph can have without containing a specified forbidden subgraph.

Saturation problems form a counterpoint to this and are much less well-understood. In these we are concerned with the minimum number of edges a graph on n vertices can have if it is saturated in the sense that adding any new edge forces some structure. This minimum is a called the saturation number. A motivating question is Tuza's conjecture which says that the saturation number for containing any fixed subgraph should vary as a function of n in a reasonably smooth way (rather than oscillating wildly with n).

The aim of this project is to tackle a number of questions around saturation, some of them motivated by Tuza's conjecture. Resolving Tuza's conjecture would be a very ambitious outcome for the project, however there are numerous possible weaker and variant questions which could be studied. These include questions concerning quantitative bounds which limit the possible behaviour of the saturation number, and constructions of slightly more general settings where the saturation number shows irregular behaviour.

Another direction is to investigate versions of saturation relative to a particular large graph (sometimes described as varying the host graph) which could be structured or generated by some random process.

Many questions in extremal graph theory have analogues in other discrete structures such as directed graphs, matrices and permutations. There has been some work in this direction but it is much less developed than for Turan-type problems. Another aspect of this project is to explore and develop the theory of saturation numbers in other combinatorial settings.

In common with many combinatorial problems, the methodology involves a mixture of direct combinatorial arguments (often requiring considerable ingenuity) and tools from other areas of mathematics such as linear algebra and probability (which often appear in surprising ways).