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
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 will be on reserve in the Reserve Reading Room (on 2-hour loan).
We meet on MWF 1:10 - 2:10 in LN-2205.
Short outline:
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.
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 (!).
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.
[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.
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.
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.
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. Additional reading (I will give you these articles):
T. Zaslavsky, Biased graphs. I. Bias, balance,
and gains.
J. Combinatorial Theory Ser. B 47 (1989), 32--52.
T. Zaslavsky, Biased graphs. II. The three matroids.
J. Combinatorial Theory Ser. B 51 (1991), 46--72.
Special makeup classes on
Thursdays Dec. 2, 9,
1:15 - 2:40 in LN-2201.
Also others to be arranged during finals week:
Tuesday Dec. 14 in LN-2206 and Wednesday Dec. 15 in LN-2205,
3:00 - 5:15 p.m. (with break).
Course Outline
Sections that we omit or skim over very lightly are: 1.8, 2.4, 6.7,
6.8.
We omit Sections II.4, II.5.
Course Work
Corrections
Textbook Corrections
"Biased graphs" Corrections
A Brief Description of Matroid Theory
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 an object, 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, a Gestalt.