Title: Bounding the diameter of polytopes using oriented matroids
and satisfiablity solvers
Author: Lars Schewe
(joint work with David Bremner, Antoine Deza, and William Hua)
Abstract:
It is a longstanding open problem to find good bounds for the diameter
of the edge graph of a d-dimensional polytope with n facets (denoted
by Delta(d,n)). One idea to tackle these questions for small
parameters is to study the problem in the more general setting of
oriented matroids. We will show how this combinatorial model can be
used to formulate the diameter question for small parameters as a
finite number of satisfiability problems. We show that Delta(6,12)=6,
implying that the Hirsch conjecture is true in the case where n-d <=
6. Additionally, we can show that Delta(4,11)=6 and Delta(4,12)=7. We
also present on-going computations for the cases Delta(5,12) and
Delta(6,13).