Math 580: Combinatorial Analysis
Matroid Theory
Fall 2001

This course is an introduction to the basic concepts and constructions of matroid theory and to the chief examples. It will be largely based on the textbook of James Oxley, Matroid Theory, Oxford University Press, 1992 (which is available at the bookstore). The book doesn't cover everything -- fortunately, if you prefer your book to be less than 1000 pages long -- but it is an exceptionally nice graduate textbook.

Click here for Assignments.

The course 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).

If you aren't sure whether you might be interested or ready for this class, please see me.

The book is on reserve in the Reserve Reading Room (on 1-day loan, I believe).

We meet on MWF 2:20-3:20 in LN-2201.

Course Outline

• Oxley, Chapters 1-6. Possibly Sections 7.1-2 (if time allows).
• Zaslavsky, "The Möbius function and the characteristic polynomial."
• Zaslavsky, "Biased Graphs I, II, IV." (For short: "BG1", "BG2", "BG4".)
  As a short summary of many (not all) main points: "Voltage-graphic Matroids". (For short: "VGM".)
  As optional supplementary reading: "The Geometry of Root Systems ..." (for short: "GRS"). Has good diagrams of hyperplane arrangements.

More details:
Sections that will be omitted or skimmed over are:

• In Oxley:
  • Chapter 1: Omit Sections 6, 8. They are worth skimming over to see more reasons people have been interested in matroid theory, but especially Section 6 is quite complicated (at any rate, I always found transversal theory to be complicated).
  • Chapter 2: Section 4.
  • Chapters 3-5: We will go lightly over Sections 4.3, 5.3, and 5.4.
  • Chapter 6: Omit Sections 7-8. Also, we will take Section 9 very lightly. Section 6.2 is really just a supplement to 6.1, not a major section in itself.
• In Zaslavsky, characteristic polynomial:
  To be announced.
• In Zaslavsky, Biased Graphs:
  To be announced.

An outline of the initial material from the course is available here, as a PostScript file. It doesn't go far or have much detail. It probably has errors. I will be happy to hear of any you find, no matter how trivial.

Course Work

I will expect you, the students, to study the material and to work on as many of the exercises as you can. I will meet separately with each student weekly to discuss your progress and any questions you may have. I will occasionally collect written work (but not often). There will not be any tests (!).

Corrections

Textbook Corrections

Here is a PostScript file of corrections for the book, prepared by the author. Some of them are simple errors, but many are improved proofs, updates on conjectures, and so on. (Oxley's homepage; at last check, his version of the corrections was the same as the one above, but he has it in PDF as well as PS.)

Here are additional corrections and comments of my own.

"The Möbius function ..." Corrections

The copy I distributed has a couple of bad spots.

• P. 123, bottom: the sum is over F \in L.
• P. 127, bottom: the ink marks at the bottom are supposed to say:
  7.5.1. Proposition. \chi(\Gamma;\lambda) = \lambda^c(\Gamma) p(M;\lambda).

"Biased graphs" Corrections

"BG1", Section 5, p. 45: In the definition of Phi/A (line 9), I forgot to say: ``Also, delete the vertices of Phi that are not in B.''

All: the ``complete lift matroid'' should better be called the ``extended lift matroid'' since it is a ``single-element extension'' of the lift matroid.

A Brief Description of Matroid Theory

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 my home page.