berkeley-combinatoricsseminar-April2020

From Jesus De Loera April 28, 2020

views comments

I gave the following lecture in Zoom (COVID 19 era):

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). Paper is available online at arXiv:2002.00999

Looking for more...

berkeley-combinatoricsseminar-April2020

Related Media