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.