Created by:

Profile Photo

Last updated:

September 23, 2022


Unlimited Duration


This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration


In this graduate-level course, we will be covering advanced topics in combinatorial optimization

We will start with non-bipartite matchings and cover many results extending the fundamental results of matchings, flows and matroids. The emphasis is on the derivation of purely combinatorial results, including min-max relations, and not so much on the corresponding algorithmic questions of how to find such objects. The intended audience consists of Ph.D. students interested in optimization, combinatorics, or combinatorial algorithms.

Course Curriculum

  • Non-Bipartite Matching Unlimited
  • Non-Bipartite Matching: Edmonds’ Cardinality Algorithm and Proofs of Tutte-Berge Formulas and Gallai-Edmonds Decomposition Unlimited
  • Cubic Graphs and Matchings, Factor-Critical Graphs, Ear Decompositions Unlimited
  • The Matching Polytope, Total Dual Integrality, and Hilbert Bases Unlimited
  • Total Dual Integrality, Totally Unimodularity Unlimited
  • Posets and Dilworth Theorem Unlimited
  • Partitioning Digraphs by Paths and Covering them by Cycles Unlimited
  • Proof of the Bessy-Thomasse Result The Cyclic Stable Set Polytope Unlimited
  • Matroids: Defs, Dual, Minor, Representability Unlimited
  • Matroids: Representability, Greedy Algorithm, Matroid Polytope Unlimited
  • Matroid Intersection Unlimited
  • Matroid Intersection, Matroid Union, Shannon Switching Game Unlimited
  • Matroid Intersection Polytope, Matroid Union Unlimited
  • Matroid Union Unlimited
  • Matroid Matching Unlimited
  • Jump Systems Unlimited
  • Graph Orientations Unlimited
  • Submodular Flows Unlimited
  • Splitting Off Unlimited
  • Proof of Splitting-Off Submodular Function Minimization Unlimited
  • Multiflow and Disjoint Path Problems Two-Commodity Flows Unlimited
  • The Okamura-Seymour Theorem The Wagner-Weihe Algorithm Unlimited

About the instructor

5 5

Instructor Rating







Profile Photo
Massachusetts Institute of Technology