Prerequisite: Knowledge of Network flows and graph theory from an undergraduate course on one of these topics or an undergraduate algorithms course.
Associated to any graph there are a number of natural polyhedra and matrices. For example, the convex hull of all the incidence vectors of the stable sets in the graph. Many key theorems in optimization involve the study of these polyhedra, in particular characterizations of when they are integral or near integral. Conversely, many properties of 0-1 polyhedra can be understood by studying an associated graph (whose adjacency matrix is the matrix $A$ in the equation Ax = b defining the polyhedra). We study theorems of this type. Although motivated by the relationship to polyhedra, most of the results we discuss involve structural decompositions of graphs.
There will be 4-5 homework assignments worth 25%. Participation in the problem solving sessions on perfect graphs will be worth 25%. There will be a midterm worth 25%, and a final worth 25%. The midterm will be October 30th.
Lovasz and Plummer (1986), Matching Theory (North Holland).
Cournejols (2000), ( Combintorial Optimization, Packing and Covering). Published by AMS-SIAM. Note this book contains 18 conjectures for each of which the author has offered US$5,000.
Ramirez-Alfonsin and Reed (2001), Perfect Graphs (Wiley).
Golumbic(1980), Algorithmic Graph Theory and Perfect Graphs (Academic Press).
Students are expected to work on the following List of Problems on Perfect Graphs. Note that this list will grow throughout the term.
A brief summary of the first lecture can be found here.
In the second lecture, we proved the Tutte-Berge Formula which states that the number of vertices missed by a maximum matching is equal to the maximum over all sets $X$ of vertices of the amount by which the number of odd components of $G-X$ exceeds $|X|$. An alternative proof can be found in Section 3.1 of Lovasz-Plummer.
In the third lecture we characterized The Matching Polytope
In the fourth lecture we discussed Matching Algorithms
In the fifth lecture we discussed fractional colouring. A paper by Kilakos and Reed on this topic was handed out
In the sixth lecture, we discusssed Perfect graphs. We proved the Weak Perfect Graph Conjecture and a strengthening due to Lovasz. A chapter by Reed called From Comjecture to Theorem which covers this material was handed out.
In the seventh lecture, we discussed an Odd Version of Hadwiger's Conjecture. A paper on this topic was handed out.
In the eigth lecture we disccused comparability graphs and even pairs. For the latter topic, pages 67-77 of the Chapter on even pairs handed out in class are a good topic. For the former, I handed out a proof of Dilworth's Theorem from Chvatal's book. I also handed out a chapter on comparability graphs which you may find heavy going. At the least this chapter contains a definition of Forcing class on the first two pages.More details of our algorithm can be found here
In the 9th lecture we talked about various classes of perfectly contractile graphs. The chapter on even pairs is a good reference for this.