Oriented matroids are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. This talk is focused on the graph whose nodes correspond to the cocircuits of the oriented matroid. This graph is a generalization of the graph of polytopes whose nodes correspond to its vertices. Graphs of polytopes were (and still are) the subject of intensive research regarding the bounds on the number of steps taken by the Simplex algorithm for solving linear programming problems.

In particular, we present an improvement on a long-standing quadratic bound on the diameter (the longest distance between two nodes on the graph) of oriented matroids, as well as several diameter bounds paralleling known bounds for polytopes.  We’ll also present a “Hirsch –type” conjecture for oriented matroids and discuss its relation to the famous Hirsch conjecture for polytopes. We’ll conclude with a surprising observation on the relevance of diameter bounds for polytopes and oriented matroids to the complexity of the simplex algorithm.

This is joint work with Jesús DeLoera, Steve Klee, and Zhenyang Zhang.