Tutte seminar - Marco di Summa

A notion of inverse Chvátal rank

Abstract:

The Chvátal rank of a polyhedron Q is the number of times one has to iterate the derivation of the so-called Chvátal closure in order to obtain the integer hull of Q, i.e., the polyhedron P defined as the convex hull of the integer points in Q. This number is known to be always finite for a fixed Q.

In this talk I will reverse this viewpoint by introducing the notion of inverse Chvátal rank: for an integral polyhedron P, the inverse Chvátal rank of P is the supremum of the Chvátal ranks of all polyhedra Q whose integer hull is P. In other words, this number describes how bad the worst linear relaxation of P is.

I will give a characterization of the integral polyhedra for which this value is finite, and discuss bounds on the inverse Chvátal rank for certain classes of integral polyhedra.

(This is joint work with Michele Conforti, Alberto Del Pia, Yuri Faenza and Rolande Grappe.)