Convex Corners and Packing Polytopes

Start Date: October 2, 2024
Event Start Time: 12:15 PM
Event End Time: 1:15 PM
Seminar Series: Graduate Combinatorics Seminar
Presenter(s): Max Aires - Rutgers University
Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
Event Additional Info: <p>See: <a href="https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html">https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html</a></p>
Presentation Type: Stand Alone Presentation
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.

Events