Topics in Matroid Theory

Department: 
Math
Course Number: 
8803-BAK
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
Typical Scheduling: 
Not regularly scheduled

Special topics course on Topics in Matroid Theory, offered in Fall 2020 by Matt Baker.

Prerequisites: 

MATH 6121 . Some background in graph theory, at the level of MATH 6014, would also be helpful.

Course Text: 

Course materials will be drawn from a variety of texts, including:

  • “Matroid Theory” by Oxley
  • “Matroids: A Geometric Introduction” by Gordon and McNulty
  • “Hodge Theory in Combinatorics” (Bull. Amer. Math. Soc. 55 (2018), 57-80)
  • “Matroids over Partial Hyperstructures” (Advances in Mathematics 343 (2019), 821-863)

 

Topic Outline: 

Definition of matroids and basic examples

Cryptomorphic descriptions of matroids (bases, circuits, flats, rank function, closure operators…)

Plücker relations and the Grassmannian, relation to the basis exchange property

Deletion and contraction, minors, duality

Combinatorial optimization and the greedy algorithm, transversal matroids, Rado’s generalization of Hall’s theorem

Whitney’s theorems on graphic matroids (characterization of planar graphs and the 2-isomorphism theorem)

Geometric lattices, the lattice of flats, and the Möbius function of a poset

Connectivity properties of matroids

Matroid union and intersection

The Tutte polynomial

Representations of matroids over fields

Most matroids are not representable over any field (Nelson’s theorem)

Ingleton’s criterion and algebraic matroids 

Regular matroids (characterizations, excluded minors, “Matroid-Tree theorem”, Jacobian group)

Oriented matroids (topological representation theorem, oriented programming duality)

The Bergman fan of a matroid and tropical linear spaces

Excluded minor characterizations of classes of matroids

Matroid quotients and strong morphisms of matroids

The homotopy theorems of Maurer and Tutte

Cryptomorphisms for weak and strong matroids over pastures

Rescaling classes, cross ratios, and the foundation of a matroid

Classification of matroids without large uniform minors 

The Chow ring of a matroid, combinatorial Hodge theory, and applications

Discrete convexity, Lorentzian polynomials, and applications