April 10, 2017

Bases with a Twist

Matroids can be seen in the bases of a vector space, especially the column space of a matrix, or the spanning forests of a graph. The sets of these structures satisfy the following property:

If B1 and B2 are bases (spanning forests) and v is a vector (e is an edge) in B1\B2, then there is a vector w (edge f) in B2/B1 such that B3=B1-v+w (B1-e+f) is also a base of the vector space (spanning forest of the graph.)

This property can be used to define matroids. In the 1980’s, Bouchet proposed a slight twist to this property and used the new property to define delta matroids.

In a matroid, you can delete and contract edges to obtain minors of the matroid. In 1971, Gian Carlo Rota conjectured that the set of matroids that arise from the column space of a matrix over a given finite field has a finite list of excluded minors. Using the Graph Minors Project of Robertson and Seymour as a starting point, Geelen, Girards, and Whittle announced in 2013 that they had proven Rota’s Conjecture. They worked on this problem for 10 years, and they are still in the process of writing the solution. This has led to a flurry of activity in matroid representation theory. Certain classes of delta-matroids also have matrix representations, but little is known about these classes except those representable over the two-element field. We will talk about further directions in this area and give a small amount of computational data for delta-matroids representable over the three-element field. This is joint work with Carolyn Chun, Deborah Chun, and Tyler Moss.