Topics in Combinatorial Optimization: Introduction to Combinatorial Optimization

This course surveys the theory of combinatorial optimization. We cover the elementary min-max theorems of graph theory, such as Konig's theorems and Tutte's matching theorem, network flows, linear programming and polyhedral optimization, hypergraph packing and covering problems, perfect graphs, polyhedral methods to prove min-max theorems, packing directed cuts, the Lucchesi-Younger theorem, Packing T-cuts, T-joins and circuits, Edmonds' matching polytope theorem, relations with the four-color theorem, Lehman's results on ideal clutters, various further topics as time permits.