Forbidden Substructures in Matroids and Graphs

拟阵和图中的禁止子结构

• 批准号: 2884208
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2884208
• 关键词: Forbidden; Substructures; Matroids; Graphs

This project is concerned with structural results relating to matroids and graphs. Matroids are combinatorial objects, first introduced in 1935 as an abstraction of graphs. They generalise several ideas from both linear algebra and graph theory, and as such, many of the techniques and ideas commonly employed in graph theory are also useful in matroid theory. In both fields, we often wish to study a class that is defined by some excluded property, such as a set of forbidden subgraphs or excluded minors. We will study a range of problems of this variety. This project falls within the EPSRC 'Logic and Combinatorics' research area.The class of GF(q)-representable matroids is fundamental to matroid theory, and many famous results relate to characterising this class for some prime power q. In 1988, Kahn conjectured that for each value of q, there is a bound on the number of inequivalent representations that a GF(q)-representable matroid may have [1]. This conjecture was later disproven, and the class of 'spikes' was found as a counterexample [2]. Spikes are now known to be essential for understanding a range of matroid behaviours, and many specific spikes, such as the Fano matroid, are of particular importance to matroid theory. Gaining a structural understanding of the class of spikes is therefore desirable to improve our understanding of the structure of other classes and specifically our understanding of representable matroids, one of the primary goals of modern matroid theory.Recent research has studied the class of matroids obtained by closing the class of spikes under minor operations, and conjectured that this class has only a finite number of excluded minors [3]. The authors pose obtaining the explicit list of these excluded minors as an open problem. We propose to solve this problem and also to characterise the set of 3-connected matroids that are minors of spikes.We also propose investigating problems of a similar description in graph theory, where we may investigate properties of classes defined by forbidden subgraphs, a less strict requirement than excluded minors. It is natural to investigate whether problems that are challenging to solve for graphs in general remain challenging if we place such a restriction on the class of input graphs. This is an active area of research for various colouring problems. The most well-known colouring problems, such as determining whether a graph is k-colourable or k-list colourable for some list assignment, are NP-complete when the class of input graphs in unrestricted. The algorithmic complexity of each of these colouring problems on classes of graph with precisely one forbidden subgraph has been fully described [4], [5]. However, many interesting problems remain. For instance, fully characterising the complexity of each of these problems when k is specified is an open problem, and much less is known about the complexity of colouring problems on classes defined by more than one forbidden subgraph. We propose to continue studying problems in this area.[1] J. Kahn, "On the uniqueness of matroid representations over GF (4)," Bulletin of the London Mathematical Society, vol. 20, no. 1, pp. 5-10, 1988.[2] J. Oxley, D. Vertigan, and G. Whittle, "On inequivalent representations of matroids over finite fields," journal of combinatorial theory, Series B, vol. 67, no. 2, pp. 325-343, 1996.[3] D. Mayhew, M. Newman, and G. Whittle, "Fractal classes of matroids," Adv Appl Math, vol. 126, p. 101995, 2021, doi: https://doi.org/10.1016/j.aam.2019.101995.[4] D. Král', J. Kratochv\'\il, Z. Tuza, and G. J. Woeginger, "Complexity of coloring graphs without forbidden induced subgraphs," in Graph-Theoretic Concepts in Computer Science: 27th InternationalWorkshop, WG 2001 Boltenhagen, Germany, June 14-16, 2001 Proceedings 27, 2001, pp. 254-262.[5] P. A. Golovach, D. Paulusma, and J. Song, "Closing complexity gaps for coloring problems on H-free graphs," Inf Comput, vol. 237, pp. 204-214, 20

该项目涉及与拟阵和图相关的结构结果，拟阵是组合对象，于 1935 年首次作为图的抽象引入。它们概括了线性代数和图论的一些思想，因此，许多技术和思想。在图论中常用的在拟阵理论中也很有用，在这两个领域中，我们经常希望研究由某些排除属性定义的类，例如一组禁止的子图或排除的子图。该项目属于 EPSRC“逻辑和组合学”研究领域。GF(q) 可表示的拟阵类是拟阵理论的基础，许多著名的结果都与表征此类的某些素数幂相关。 1988 年，Kahn 推测对于每个 q 值，GF(q) 可表示的拟阵可能具有的不等价表示的数量存在一个界限 [1]。这个猜想后来被证明是错误的，并且发现“尖峰”类别作为反例 [2] 现在已知尖峰对于理解一系列拟阵行为至关重要，并且许多特定的尖峰（例如法诺拟阵）具有特殊性。因此，获得对尖峰类别的结构理解有助于提高我们对其他类别结构的理解，特别是对可表示拟阵的理解，这是现代拟阵理论的主要目标之一。研究研究了通过在次要操作下关闭尖峰类而获得的拟阵类，并推测该类只有有限数量的排除次要项[3]。作者将获取这些排除次要项的明确列表作为一个开放问题。我们建议解决这个问题，并描述作为尖峰次要的 3 连通拟阵的集合。我们还提出了图论中类似描述的问题，其中我们可以研究由禁止子图定义的类的属性，a less。如果我们对输入图的类别进行这样的限制，那么很自然地要研究通常难以解决的图问题是否仍然具有挑战性，这是各种着色问题的活跃研究领域。当输入图的类别不受限制时，大多数著名的着色问题（例如确定图是否为 k 着色或 k 列表着色）都是 NP 完全的。关于图的类别精确地描述了一个禁止子图[4]，[5]，但是，仍然存在许多有趣的问题，例如，在指定 k 时充分描述每个问题的复杂性是一个悬而未决的问题，而且知之甚少。关于由多个禁止子图定义的类的着色问题的复杂性，我们建议继续研究这一领域的问题。[1]“论 GF (4) 上拟阵表示的唯一性”。伦敦数学会，第 20 卷，第 1 期，第 5-10 页，1988 年。[2] J. Oxley、D. Vertigan 和 G. Whittle，“关于有限域上拟阵的不等价表示”，组合理论杂志，B 系列，第 67 卷，第 325-343 页，1996 年。[3]和 G. Whittle，“拟阵的分形类”，Adv Appl Math，第 126 卷，第 101995 页，2021 年，doi：https://doi.org/10.1016/j.aam.2019.101995。 ”、J. Kratochv\'\il、Z. Tuza 和 G. J. Woeginger， “没有禁止诱导子图的着色图的复杂性”，载于计算机科学中的图论概念：第 27 届国际研讨会，WG 2001 德国博尔滕哈根，2001 年 6 月 14-16 日，论文集 27，2001 年，第 254-262 页。[5] Golovach、D. Paulusma 和 J. Song，“缩小复杂性差距无 H 图上的着色问题，《Inf Comput》，第 237 卷，第 204-214 页，20