Monotone paths on cross-polytopes
- Alex Black (UC Davis, Davis, USA)
Abstract
In the early 1990s, Billera and Sturmfels introduced monotone path polytopes (MPPs). MPPs encode the combinatorial structure of paths potentially chosen by the simplex method to solve a linear program on a given polytope for a fixed linear functional. In their original paper, they showed that MPPs of simplices and cubes for any generic linear functional are combinatorial cubes and permutahedra respectively. The natural next question to ask is: What are the MPPs of cross-polytopes for generic linear functionals? I will present a complete characterization of MPPs of cross-polytopes for generic linear functionals and show how this result informs our understanding of MPPs of centrally symmetric polytopes. This talk is based on joint work with Jesús De Loera.
