In some sense, matroids are generalisations of graphs. The idea of graph minors extends to matroids, and so does the idea of a minor-closed class. We can think of a minor-closed class of matroids as being an analogue to the class of graphs embeddable on a surface. Any such class of graphs has a corresponding class of minimal forbidden minors, and these forbidden minors characterise the class. A minor-closed class of matroids is characterised by its minimal forbidden minors in the same way.
Rota’s conjecture is the most famous problem in matroid theory. It says that when F is a finite field, there is a finite number of minimal forbidden minors for the class of matroids that can be represented by vectors over the field of scalars F. A proof has been announced by Geelen, Gerards, and Whittle.
Gain-graphic matroids are analogues to matroids represented by vectors: instead of representing the matroid using numbers from a field, we use elements from a group. So we can ask for an analogue of Rota’s conjecture, except for gain-graphic matroids.
In this talk I will outline our intended path towards Rota’s conjecture for gain-graphic matroids. This is joint work with Daryl Funk.
On January 28, 2020, Dillon Mayhew from Victoria University of Wellington, New Zealand gave a talk on problems and results motivated by Courcelle’s theorem, with an emphasis on hypergraphs and matroids. The title of his talk is “Courcelle’s Theorem for hypergraphs“.
Courcelle’s Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity…), so Courcelle’s Theorem implies that these difficult properties can be tested in polynomial time when the structural complexity of the input is limited.
Matroids can be considered as a special class of hypergraphs. Any finite set of vectors over a field leads to a matroid, and such a matroid is said to be representable over that field. Hlineny produced a matroid analogue of Courcelle’s Theorem for input classes with bounded branch-width that are representable over a finite field.
We have now identified the structural properties of hypergraph classes that allow a proof of Hliněný’s Theorem to go through. This means that we are able to extend his theorem to several other natural classes of matroids.
This talk will contain an introduction to matroids, monadic logic, and tree-automata.
This is joint work with Daryl Funk, Mike Newman, and Geoff Whittle.
