Matroid Theory

Fall 2023

To the assignments | extra material | corrections page.

Office: WH-216

Email: zaslav@math.binghamton.edu

Class meets on M, W, F at 3:30 in WH-309. I also meet each student individually every week.

This course is an introduction to the basic concepts and constructions of matroid theory and to the chief examples. This is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course in that).

The course is based on:

- James Oxley, Matroid Theory, second edition,
Oxford University Press, 2011. (Do not use the first edition.)

The book doesn't cover everything; but it is an exceptionally good graduate textbook. - Lectures and readings about hyperplane arrangements, chromatic (for graphs) and characteristic (for arrangements) polynomials, and signed, gain, and biased graphs.

- Background
- Oxley, Preliminaries section before Chapter 1. This is essential knowledge about graphs, finite fields, and more.

- Matroids
- Oxley, Chapters 1–6 (with some omissions). Almost all of Chapters 1-4 is fundamental.
- Ch. 1 (omit §6 and §8).
- Ch. 2 (omit clutters and §4).
- Ch. 3 (omit transversal matroids and gammoids and spikes).
- Ch. 4 (omit most of §3).
- Ch. 5
- §1.
- §2: to statement of Th. 5.2.2, and Cor. 5.2.6.
- §3: to statement of Th. 5.3.1, and Prop. 5.3.7.

- Ch. 6
- §§1-3.
- §4: the Fano and non-Fano matroids (definitions, and statements of 6.4.4 and 6.4.8).
- §5: statements of 6.5.1-5.
- §6: to statement of 6.6.3.
- §9: to statement of 6.9.1. This shows another way projective geometries are especially important matroids.
- §10 (omit proof of Th. 6.10.10).

- Possibly Ch. 7: §§7.1-2.

- Oxley's errata for this edition (as of 2020).
- An outline of the initial material on matroids is here. I will be happy to hear of any errors.

- Oxley, Chapters 1–6 (with some omissions). Almost all of Chapters 1-4 is fundamental.
- Invariants
- Zaslavsky, "The Möbius function and the characteristic polynomial", Chapter 7 of Combinatorial Geometries, ed. by Neil White.

Read §§1-2; §3 up to Theorem 7.3.2 (inclusive); in §5 the first and third examples.

- Zaslavsky, "The Möbius function and the characteristic polynomial", Chapter 7 of Combinatorial Geometries, ed. by Neil White.
- Hyperplane Arrangements
- Signed, Gain, and Biased Graphs
- Basics of signed graphs and their matroids: "Signed graphs".
- Coloring and orientation of signed graphs and the chromatic quasipolynomial: "Signed graph coloring".
- Problems about circles in signed graphs for amusement and possibly one or two assigned problems.
- Sketchy introduction to gain graphs and matroids: "Voltage-graphic matroids" (now called gain graphs and frame matroids).
- Basics of gain graphs: "Biased graphs. I. Bias, balance and gains".
- Frame matroids of gain graphs: "Biased graphs. II. The three matroids", section 2

(should have been "The two matroids", cf. LotR vol. 2). - Applied to hyperplane arrangements: "An elementary chromatic reduction for gain graphs and special hyperplane arrangements".

- I will post additional corrections as we find them and as the course progresses. Link to the corrections page.

Optional additional reading:

- A condensed introduction to matroids by Oxley.
- A possibly helpful supplement is the undergraduate textbook Matroids: A Geometric Introduction by Gary Gordon and Jennifer McNulty, Cambridge University Press, 2012. It may help you to get better intuition.
- For a signed-graphic proof of Tutte's characterization of regular matroids, see Gerards' paper.

I expect you, the students, to study the material and to work on as many of the exercises as you can. I'll collect written work every week or two and return it with comments, for your edufication. There will not be any tests! I'll meet separately with each student frequently to discuss your progress and any questions you may have.

What is a matroid, really? A matroid is not one thing; it is a complex of properties, no one of them most important. Here is a description of a function, which could be said just as well of a matroid.

A function was not, for Riemann, a mere set of points; still less was it any of its pictorial representations as a graph or a table; and still less a collection of expressions involving algebraic formulas. ... What then, was a function? It was anobject, from which none of its attributes could properly be detached. Riemann saw a function the way chess grandmasters are said to see a game, all at once, as a unified whole, aGestalt.– Prime Obsession by John Derbyshire, 2003, p. 129.

Matroid theory originated as an abstract study of the properties of linear dependence of finite sets of vectors in a vector space. The idea was to forget the details of linear dependence relations and only remember which sets of vectors are linearly dependent. There are some nice axioms to describe a property abstracting linear dependence – let's call it ``dependence'' – that allow one to define (purely abstractly) such basic vector-space properties dimension (we call it ``rank''), linearly closed sets, bases, and much more. The main thing they don't allow one to do is to find the vector space, because the axioms admit examples that cannot possibly come from vectors. A set with a list of dependent subsets (or an equivalent, like a rank function or a list of bases) is called a matroid.

Another origin of matroid theory is in graph theory. There is a natural matroid on a graph: the elements of the matroid are the edges of the graph and the dependent subsets are the edge sets that contain a circuit (a.k.a. cycle or closed path). Many interesting and important graph properties are naturally expressed in terms of matroids. For instance, a spanning tree of a graph is the same as a basis of the graphic matroid. The chromatic polynomial of a graph (this counts proper colorings; it appeared in an attempt to prove the Four-Color Theorem) is another thing that is essentially matroidal, although the connection is less simple. Graph connectivity is closely related to matroids, although here there are some complications.

There are many other sources of matroid theory and examples, including hyperplane arrangements (which have their own analogs of chromatic polynomials), transversals, and whatever.

To the assignments | extra material | corrections page.

To my home page.