You are here

The space of monotone paths of a linear program

Jesús A. De Loera, University of California, Davis
Wednesday, October 28, 2020 - 3:30pm to 5:00pm
via Zoom
Jesus A. De Loera

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10. 

Join Zoom Meeting:
Meeting ID: 950 2088 4635

Given a polytope \$P\$ and linear function \$f\$ (this pair makes a linear program). We investigate the possible monotone paths inside the oriented graph of \$P\$ (oriented by the objective function \$f\$). We consider both the shortest and the longest monotone paths possible and estimate the (monotone) diameter and the height of some famous combinatorial polyhedra (such as TSP, fractional matching polytopes, and others). As we look at the set of all monotone paths put together we see a rich topological CW-space structure which was first studied by Billera and Sturmfels in their theory of fiber polytopes and can be used to count how many monotone path are there or to generate them randomly. Our main enumerative results include bounds on the number of monotone paths, and on the flip diameter of the CW-complex of monotone paths (how far are two monotone paths from each other?). The picture is fairly complete in dimension three, but plenty of open problems remain for high dimensional polytopes. These new theorems presented in my talk com from two papers, the first joint work with Moise Blanchard (MIT) and Quentin Louveaux (U. Liege) and the second joint work with Christos Athanasiadis (U. Athens) and Zhenyang Zhang (UC Davis)