Fragile matroids and excluded minors

Fragile matroids and excluded minors

-
Dillon Mayhew, Victoria University of Wellington
Fine Hall 224

Matroids abstract the notions of linear/geometric/algebraic dependence. 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, and distinguish the linearly dependent subsets, then the result is a matroid, and we say that such a matroid is representable. 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. The classical approach to characterizing representable matroids has involved excluded minors. Matroid minors are analogues of graph minors, in that there are two ways we can remove an element from a matroid: deletion and contraction, and a minor is a matroid produced by a sequence of such operations. An excluded minor for a class of representable matroids is a minor-minimal matroid that is not in the class. Thus a matroid belongs to the class if and only if it contains no excluded minor. The most famous example of an excluded-minor theorem is the Kuratowski-Wagner characterization of planar graphs. This talk focus on the matroid property of fragility, and its possible use in finding new excluded-minor characterizations. Knowledge of matroids will not be assumed: concepts will be introduced as required. This is joint work with Geoff Whittle, Stefan van Zwam, and others.