Graph theory seminar - Ahmad Abdi

The Set Packing and Set Covering Polyhedra

Abstract:

The set packing and set covering polyhedra are two of the most fundamental objects in combinatorial optimization. More than 50 years of studying the different properties of these objects has led to many beautiful theories and spectacular results, such as Fulkerson's theory of blocking and anti-blocking polyhedra, the different perfect graph theorems, characterization of ideal matrices, matroids with the max-flow min-cut property, characterization of weakly bipartite graphs, and many more.

In this talk, I will give an overview of these results, and explain the striking differences between the two objects that makes the set covering polyhedron much more complex than the other one. I will also talk about some recent progress towards understanding these polyhedra.

Some of the results are based on joint works with A. Feldmann,
R. Fukasawa, B. Guenin, J. Könemann and L. Sanità.