Jesus de Loera: Combinatorics in the Space of Monotone Paths of a Convex Polytope
Abstract
Using a linear functional f on a convex polytope
P induces an orientation on the graph of P. Vertices are ordered by f and
all the faces of P are oriented with a unique sink and a unique source. On the resulting
directed graph one can define f-arborescences (directed single-sink spanning trees) and f-monotone paths on P (directed paths respecting the order of vertices), as well
as natural graph and CW complex structures on the set of f-monotone paths
These objects are important in geometric combinatorics (Baues complexes and polyhedral subdivisions studied by Billera, Sturmfels, Gelfand, Kapranov, Zelevinsky and others in the early 1990’s) and in discrete optimization (In particular the complexity of the simplex method with work going back to Klee). In my talk I will discuss some natural counting problems associated with the discrete geometric situation.
Our main results include bounds on the extreme values of the number of f-arborescences,
the number of f-monotone paths, and the diameter of the graph of
f-monotone paths for polytopes P in terms of their dimension and
number of vertices. The picture is fairly complete in dimension three, but plenty of open problems remain. This is joint work with Christos Athanasiadis (U. Athens) and Zhenyang Zhang (UC Davis).