Forbidden Substructures in Matroids and 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