On the Diameter of Polytopes
On the Diameter of Polytopes
-
Benjamin Matschke, IAS
Fine Hall 224
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.