Matroids are the abstract objects that lie behind various notions of dependence (linear, geometric, algebraic), in the same way that topologies lie behind various notions of continuity. More specifically, a matroid consists of a finite collection of points and a distinguished family of dependent subsets. If we take a finite collection of vectors from a vector space (over a field F), and distinguish the linearly dependent subsets, then the result is a matroid, and we say that such a matroid is representable (over F). The original motivating problem in matroid theory involves deciding which matroids are representable and which are not. A large fraction of the research in the area has been driven by this problem.
This talk will be both an introduction to matroid theory and an examination of two different methods for characterizing representable matroids. The first method involves excluded minors. Matroid minors are exact analogues of graph minors: we can remove an element from a matroid by deleting or contracting it, and any matroid produced by a sequence of these operations is called a minor. The class of matroids representable over a field is closed under the operations of deletion and contraction, and therefore can be characterised by listing the minor-minimal matroids not in the class, that is, the excluded minors for the class. This approach is analogous to the Kuratowski–Wagner characterisation of planar graphs. The second approach to characterising representable matroids involves the use of formal languages – can we add axioms to the list of matroid axioms in such a way that we exactly capture the class of representable matroids? This approach has not received nearly as much study, but there have been some recent developments.
No knowledge of matroids will be assumed.