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）-可表示拟阵类是拟阵理论的基础，许多著名的结果都与刻画这类拟阵的素数幂q有关。在1988年，Kahn证明了对于每个q值，GF（q）-可表示拟阵可能具有的不等价表示的数目有一个界[1]。这个猜想后来被证明是错误的，而“尖峰”类被发现作为一个反例[2]。现在已知尖峰对于理解一系列拟阵行为是必不可少的，并且许多特定的尖峰，例如Fano拟阵，对拟阵理论特别重要。因此，对尖峰类的结构有一个更好的理解，可以帮助我们更好地理解其他类的结构，特别是我们对可表示拟阵的理解，这是现代拟阵理论的主要目标之一。最近的研究研究了通过对尖峰类进行小运算而得到的拟阵类，并证明了该类只有有限个被排除的小运算[3]。提交人提出，获得这些被排除在外的未成年人的明确名单是一个悬而未决的问题。我们建议解决这个问题，也是一组3-连通拟阵的未成年人的spikes.We还建议调查问题的一个类似的描述在图论中，我们可以调查性质的类定义的禁止子图，一个不太严格的要求比排除未成年人。如果我们对输入图的类设置这样的限制，那么很自然地会调查通常对于图来说具有挑战性的问题是否仍然具有挑战性。这是研究各种着色问题的活跃领域。最著名的着色问题，如确定一个图是否是k-列或k-列表列的一些列表分配，是NP-完全的输入图类不受限制。在含有一个禁止子图的图类上，每一个着色问题的算法复杂性已被充分描述[4]，[5]。然而，许多有趣的问题仍然存在。例如，充分刻画这些问题的复杂性，当k是指定的是一个开放的问题，和更少的是已知的复杂性着色问题的类定义的一个以上的禁止子图。我们建议继续研究这方面的问题。[1]J. Kahn，“On the unique of matroid representations over GF（4），”Bulletin of the伦敦数学学会，第20卷，第1期，第110页。1988年5月10日[2]奥克斯利，D. Vertigan和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.纽曼和G. Whittle，“拟阵的分形类”，Adv Appl Math，第126卷，第101995页，2021年，doi：https://doi.org/10.1016/j.aam.2019.101995。[4]D. Král'，J. Kratochv '\il，Z. Tuza和G. J. Woeginger，“Complexity of coloring graphs without forbidden induced subgraphs，”in Graph-Theoretic Concepts in Computer Science：27th InternationalWorkshop，WG 2001 Boltenburg，德国国，2001年6月14-16日Proceedings 27，2001，pp. 254-262. [5]P. A. Golovach，D. Paulusma和J. Song，“Closing complexity gaps for coloring problems on H-free graphs”，Inf Comput，vol. 237，pp. 204-214，20