Math 580: Topics in Combinatorics
Graphs and Combinatorial Invariants
(Ideas of W.T. Tutte)

Spring 2004

This course is an introduction to some advanced aspects of graph theory and to Tutte invariants of graphs and matroids. We will study initially portions of the book

W.T. Tutte,
Graph Theory,
Cambridge University Press.
(Here are some corrections to the book, which has remarkably few errors altogether.) We will then introduce matroids and study their invariants. For this one can consult
James Oxley,
Matroid Theory,
Oxford University Press,
or other sources; most of what we will do on matroids is not found in Oxley's book but is in research papers and in the volumes
Neil White, editor,
Combinatorial Geometries, Ch. 7, and
Matroid Applications, Ch. 6,
Cambridge University Press.

The focus of the course is on some contributions of Tutte, arguably the greatest graph theorist of the last century (neglecting Robertson and Seymour as transcenturial), and work that follows in his spirit. Some light reading about Prof. Tutte:

The course is not normally suitable for first-year graduate students. However, the only specific prerequisites are the traditional "mathematical maturity" and familiarity with groups, rings, and fields; and basic graduate algebra is very helpful.

Course time and place:

PLACE: LN-2205
TIME: Mon., Wed., Fri. 2:20-3:20.

Makeup Classes

Friday, April 23, 3:30-4:30 p.m. in LN-2205.
Thursday, April 29, 4:30-5:30 in LN-2205.
Thursday, May 6, 1:15-2:30 in LN-2205.
Finals week: Wednesday, May 12, 1:00-2:30 in LN-2205.

Office hours:

My regular office hours, which are mainly for the undergraduates, are

M, W, F: 1:20-2:00, 4:30-5:30
Th: 1:30-2:30
I will be happy to see you at these or other times as far as possible. If necessary we can make appointments.

The Combinatorics Seminar

All students are encouraged to attend the Combinatorics Seminar, time to be announced. There will be talks you can't understand, as well as some you can't help understanding, on all kinds of topics in graph theory and other combinatorics as well as in number theory (and sometimes both at once). (You'll be surprised how much you learn by not understanding a great many talks.)

Course Procedure

I will lecture, for the most part.

Student work: You will have to work hard sometimes to understand the lectures and readings. Keep your colored pencils handy. Your grade will be based on handed-in problems and (possibly) presentations. I will also meet with each of you individually on a semiregular basis.

I expect you to try all the exercises at the end of the chapters and the additional exercises (below). You don't have to solve all of them! I will collect your written solutions to some or all of the following assignments, some from Tutte and some from the additional problems. The list of hand-in problems is not compulsory but you should turn in as many as you can. You may submit second solutions of any problems to raise your grade.

Rules for write-ups that you hand in: Submit each different problem on a separate piece of paper. If you need more than one paper, staple them together. (Thank you. This will greatly assist both of us in the homework procedures.)

Due Dates

The last dates for accepting homework from each part of the course. There will be no exceptions barring medical or other disaster.

Ch. I: Friday, March 26.
Ch. II: Friday, April 2.
Ch. III: Wednesday, April 14.
Ch. VII: Friday, April 23 (5:30 p.m.).
Ch. IX: First tries: Wednesday, May 5 (5:30 p.m.). If you turn in a solution later, and I manage to return it before the final deadline, you may turn in a second version. Final versions: Thursday, May 13 (5:00 p.m.).

One reason for having deadlines is that you will have presentations to do in class toward the end of the term, and you won't be able to handle your work if you let it pile up. Another reason is that most of you have not been handing in the homework. A third reason is that I can only grade so much at once, and I have to be done before the grades are due.

Syllabus and Assignments

The syllabus is tentative and partial. It will get filled out and corrected as the course progresses.

To my home page.