Monadically defined classes of gain-graphic matroids

Sapir Ben-Shahar (University of Wisconsin-Madison)

Matroids are combinatorial structures that generalise the idea of (in)dependence, such as linear independence of vectors in vector spaces over some field. Matroids arise in a number of different contexts, including from vectors in vector spaces, graphs, points in a geometry, and as models of strongly minimal theories (among others). This talk will focus on gain-graphic matroids, which are matroids that arise from group-labeled graphs. Gain-graphic matroids are important in the study of structural matroid theory. It turns out that for “nice enough” classes of matroids, properties that are definable in monadic second-order logic can be recognized in polynomial time. Whether a class of gain-graphic matroids is definable or not depends on which group is chosen to label the graphs. This talk will give a brief introduction to matroids and monadic second order logic, and then describe recent progress on the definability question for gain-graphic matroids.

 Overview  Program