Math 581: Topics in Graph Theory: Matching Theory
Fall 2010

Syllabus

To the main course page.

The textbook is Matching Theory by László Lovász and Michael D. Plummer (republished by the American Mathematical Society).

This syllabus is a record of what we actually cover in the course. It will be complete only after the course is done. The following list is what I hope to cover, and will be modified as we go. It's not likely we can do all of it.

• Overview of matchings (Preface).
• Basic graph theory (Basic terminology).
• Matchings in bipartite graphs (Ch. 1).
• Network flows (Ch. 2).
• Maximum matchings (Ch. 3).
• Bipartite perfect matching (Ch. 4).
• General perfect matching (Ch. 5).
• The postman problem (Sect. 6.5).
• Optimization by linear programming (Sects. 7.1-7.3).
• Edmonds' matching algorithm (Sect. 9.1): approximate outline only.

To the main course page.

To my home page.