Mini-Kurse Wintersemester 2003/2004:

Stable Sets and Polyhedral Combinatorics


Mondays and Thursdays, 14.00 - 16.00 c.t.

Six sessions, starting November 20th

at the MPI (Building 46), Room 023




A coloring of a graph

Introduction:

The maximum  weight stable set  problem can, on a  perfect graph, be solved in polynomial time. This class of graphs contains, among others, bipartite graphs, comparability graphs, chordal graphs, Meyniel graphs and many others. Recently, Chudnovsky, Robertson, Seymour and Thoms proved the famous perfect graph conjecture:
  "A graph is perfect if and only if it contains no odd hole and no odd antihole"
The proof of this theorem  and its pre-proof work are impressive  examples of how  deep the field of Combinatorial Optimization has grown. We will NOT cover the proof in this course. Instead, we will start to dig into this beautiful theory. The course follows closely chapters 64-66 of the book Combinatorial Optimization, Polyhedra and Efficiency  by Alexander Schrijver.


Topics:


Colouring and  Cliques, Complexity
Basics of Polyhedral Theory
The (weak) perfect graph theorem
Examples of perfect graphs
The Lovasz theta function
Solving the maximum stable set
problem for perfect graphs