The space of monotone paths of a linear program

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)