Saturation problems on Graphs and Other Combinatorial Structures

图和其他组合结构的饱和问题

• 批准号: 2436102
• 金额: --
• 依托单位: Queen Mary University of London
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2436102
• 关键词: Saturation; problems; Graphs; Other; Combinatorial

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

图是由一组点（称为顶点）组成的离散数学结构，其中一些点对由边连接。极值图论关注的是图的哪些全局参数（如边数）迫使图具有某种结构。一个经典的例子是曼特尔定理，它确定了一个没有三角形（三个链接的顶点）的n个顶点的图可以拥有的最大边数。曼特尔定理是图兰型极值问题理论的起点。这些问题涉及到确定一个图在不包含特定的禁止子图的情况下可以拥有的最大边数。饱和问题形成了与此相对的问题，并且不太容易理解。在这些中，我们关注的是一个n个顶点的图所能拥有的最小边数，如果它是饱和的，在这个意义上，添加任何新的边都会迫使某些结构。这个最小值称为饱和数。一个激励性的问题是Tuza猜想，它说包含任何固定子图的饱和数应该以合理平滑的方式作为n的函数变化（而不是随n疯狂振荡）。这个项目的目的是解决一些关于饱和度的问题，其中一些是由Tuza猜想激发的。解决图扎猜想将是一个非常雄心勃勃的结果，但有许多可能的较弱和变体的问题，可以研究。这些问题包括有关限制饱和数可能行为的定量界限的问题，和构造稍微更一般的设置，其中饱和度数显示不规则的行为。另一个方向是研究相对于特定的大型图的饱和度版本（有时被描述为改变主机图）极图理论中的许多问题与其它离散结构如有向图、矩阵、置换等具有相似性。有一些工作在这个方向上，但它是远远低于发展比图兰型问题。这个项目的另一个方面是探索和发展其他组合环境中的饱和数理论。与许多组合问题一样，该方法涉及直接组合参数（通常需要相当的独创性）和其他数学领域的工具，如线性代数和概率（经常以令人惊讶的方式出现）。