Forbidden Substructures in Matroids and Graphs

这个项目关注与拟阵和图有关的结构结果。拟阵是组合对象，于1935年作为图的抽象而首次引入。它们概括了线性代数和图论中的一些思想，因此，图论中常用的许多技术和思想也适用于拟阵理论。在这两个领域中，我们经常希望研究由某些排除属性定义的类，例如一组禁止子图或排除子图。我们将研究这一类的一系列问题。该项目属于EPSRC的“逻辑和组合学”研究领域。GF(q)可表征的类矩阵是类矩阵理论的基础，许多著名的结果都与描述该类的素数幂q有关。1988年，Kahn推测对于每一个q值，GF(q)可表征的类矩阵可能具有的不等价表示的个数有一个界限。这个猜想后来被证明是错误的，而“尖峰”类被发现作为反例[2]。现在已知尖峰对于理解一系列拟阵行为至关重要，许多特定的尖峰，如Fano拟阵，对拟阵理论特别重要。因此，获得对尖峰类的结构理解对于提高我们对其他类的结构的理解，特别是我们对可表征拟阵的理解是可取的，这是现代拟阵理论的主要目标之一。最近的研究已经研究了在次要操作下，通过闭合尖峰类得到的拟阵类，并推测该类只有有限个数的排除次要类[3]。作者认为，获得这些被排除在外的未成年人的明确名单是一个悬而未决的问题。我们提出了解决这个问题的方法，并刻画了一组3-连通的小尖峰拟阵。我们还建议研究图论中类似描述的问题，其中我们可以研究由禁止子图定义的类的性质，这是一个比排除子图更严格的要求。如果我们对输入图的类别设置了这样的限制，那么很自然地要调查对于图来说具有挑战性的问题是否仍然具有挑战性。这是一个研究各种着色问题的活跃领域。当输入图的类别不受限制时，最著名的着色问题是np完全的，例如对于某些列表分配，确定图是k可着色的还是k列表可着色的。在具有一个禁止子图的图类上，这些着色问题的算法复杂度已经被充分描述[4]，[5]。然而，仍然存在许多有趣的问题。例如，当k被指定时，充分描述这些问题的复杂性是一个开放问题，而对于由多个禁止子图定义的类上的着色问题的复杂性知之甚少。我们建议继续研究这方面的问题J. Kahn，“关于GF(4)上的矩阵表示的唯一性”，《伦敦数学学会学报》，vol. 20, no. 5。1, 5-10页，1988J. Oxley， D. Vertigan，和G. Whittle，“有限域上拟阵的不等价表示”，《组合理论学报》，B辑，第67卷，no。2，第325-343页，1996D. Mayhew， M. Newman，和G. Whittle，“矩阵的分形类”，Adv应用数学，vol. 126, p. 101995, 2021, doi: https://doi.org/10.1016/j.aam.2019.101995.[4] D. Král’，J. Kratochv\ \il， Z. Tuza，和G. J. Woeginger，“没有禁止诱导子图的着色图的复杂性”，在计算机科学中的图论概念：第27届国际研讨会，WG 2001 Boltenhagen，德国，6月14-16日，2001论文集27,2001,pp. 254-262P. A. Golovach， D. Paulusma， J. Song，“H-free图上着色问题的复杂度缺口闭合”，《计算机工程》，vol. 37, pp. 204- 214,20

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