Subscribe to Events

Abstract: A convex corner is a convex set contained in R_{>= 0}^n which is also a downset (under the product order). A VIP among convex corners is the vertex packing polytope P(G), which is the convex hull of the vectors of the form 1_I where I is any independent set in G. The packing polytope P(G) is central to the theory of combinatorial optimization; in particular, its facets have a nice characterization when G is perfect, which leads to efficient algorithms for many problems on perfect graphs. We shall discuss the geometry of this object, and in particular its relation to another polytope, the order polytope, showing how purely geometric facts can have neat applications to posets.