Speaker:  Patricia Hersh, North Carolina State University
Title: Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
Time: 2:30 PM, Monday, May 7, 2018
Place:  Malott 206

Abstract: Given a polytope P and generic linear functional c, one obtains a directed graph G(P,c) by taking the 1-skeleton of P and orienting each edge e(u,v) from u to v for c(u) < c(v). We will discuss the question of finding sufficient conditions on P and c so that G(P,c) will not have any directed paths which revisit a face of P after departing from it. This is equivalent to the question of finding conditions on P and c under which the simplex method for linear programming will be efficient under all choices of pivot rules. Conditions are given which provably yield a corollary of the desired nonrevisiting property. One of the proposed conditions is that G(P,c) be the Hasse diagram of a partially ordered set, which is equivalent to requiring nonrevisiting of 1-dimensional faces. This opens the door to the usage of poset-theoretic techniques. This also leads to a result for simple polytopes in which G(P,c) is the Hasse diagram of a lattice L that the order complex of each open interval in L is homotopy equivalent to a ball or a sphere, with applications to weak Bruhat order, the Tamari lattice and Cambrian lattices. We will tell this story, providing background and history along the way.