Saturation problems on Graphs and Other Combinatorial Structures

图是一个离散的数学结构，由一组点（称为顶点）组成，其中一些点对由边连接。极值图论关注的是图的全局参数（如边数）使图具有一定的结构。一个经典的例子是曼特尔定理，它决定了一个有n个顶点而没有三角形（三个相连的顶点）的图可以拥有的最大边数。曼特尔定理是一个完善的图兰型极值问题理论的起点。这些是关于在不包含指定禁止子图的情况下确定图可以拥有的最大边数。饱和问题形成了与此相反的观点，人们对它的理解要少得多。在这种情况下，我们关心的是一个有n个顶点的图的最小边数，如果它是饱和的，即添加任何新的边都会强制一些结构。这个最小值称为饱和数。一个激励问题是Tuza的猜想，它说包含任何固定子图的饱和数应该以一种相当平滑的方式作为n的函数变化（而不是随着n剧烈振荡）。这个项目的目的是解决一些关于饱和的问题，其中一些是由Tuza的猜想引起的。解决Tuza的猜想对于这个项目来说将是一个非常雄心勃勃的结果，但是还有许多可能的弱问题和不同的问题可以研究。这些问题包括有关限制饱和数可能行为的定量界限的问题，以及稍微更一般的设置结构，其中饱和数显示不规则行为。另一个方向是研究相对于特定大图（有时被描述为变化的主图）的饱和版本，这可能是由一些随机过程构建或生成的。极值图论中的许多问题在其他离散结构如有向图、矩阵和置换中都有类似的问题。在这方面已经有了一些工作，但与解决图兰问题相比，进展还远远不够。这个项目的另一个方面是探索和发展饱和数理论在其他组合设置。与许多组合问题一样，该方法涉及直接组合论证（通常需要相当的独创性）和来自其他数学领域的工具，如线性代数和概率论（通常以令人惊讶的方式出现）的混合。

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).