2/25/2012

Benjamin Matschke
IAS/Princeton University

On the diameter of polytopes

Santos' construction of counter-examples to the Hirsch conjecture is based on the existence of prismatoids of dimension d of width greater than d. The case d=5 being the smallest one in which this can possibly occur, we here study the width of 5-dimensional prismatoids, obtaining the following results: - There are 5-prismatoids of width six with only 25 vertices, versus the 48 vertices in Santos' original construction. This leads to lowering the dimension of the non-Hirsch polytopes from 43 to only 20. - There are 5-prismatoids with n vertices and width \Omega(n^(1/2)) for arbitrarily large n. This is joint work with Francisco Santos and Christophe Weibel.