Combinatorics Seminar: Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology

Wednesday, February 10 at 3:00pm to 4:00pm

This is a past event.
Virtual Event

Patricia Hersh, University of Oregon

Abstract: Given a polytope P and a nonzero vector c, the question of which point in P has largest inner product (or smallest inner product) with c is the main goal of linear programming in operations research.  Key to efficiency questions regarding linear programming is the directed graph G(P,c) on the 1-skeleton of P obtained by directing each edge e(u,v) from u to v for c(u) < c(v) and in particular the diameter of G(P,c).  We will explore the question of finding sufficient conditions on P and c to guarantee that no directed path ever revisits any polytope face that it has left; this is enough to ensure that linear programming is efficient under all possible choices of pivot rule.  It turns out that poset-theoretic techniques and poset topology can help shed light on this question.  In discussing work on this question, we will provide background along the way.

Dial-In Information

Please see your email to join via zoom

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity