Special Topics: Combinatorial Optimization
Course Number: 47853
Menger (1927) showed that the maximum number of disjoint st-paths is equal to the minimum cardinality of an st-cut. Dilworth (1950) proved that the minimum number of chains needed to cover a poset is equal to the maximum cardinality of an antichain. These classic results are what started the field of Packing and Covering. In this course, we will see many theorems of this form, and study the underlying graph theoretic and geometric attributes that lead to such min-max and max-min results.
Concentration: Operations Research
Academic Year: 2019-2020
Semester(s): Mini 3