Discrete Mathematics and Optimization Seminar

---

SAMUEL FIORINI
Universite Libre de Bruxelles and GERAD - HEC
Monday March 1st at 4.30pm
Burnside 1205



Title. How to Recycle your Facets.

Abstract. A fundamental question in polyhedral combinatorics is to determine the facets of a (convex) polytope
whose vertices are given. This question often turns up to be extremely difficult. In this talk, we try to explain why.
We define a procedure transforming any facet of any 0/1-polytope into a facet of the acyclic subdigraph polytope
(a cousin of the linear ordering polytope). This result continues the line of research initiated by Billera and
Sarangarajan in 1996. They have shown that every 0/1-polytope appears as a face of the asymmetric traveling
salesman polytope provided that n is large enough.