The Maximum Diameter of Oriented Matroids
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.
Ilan Adler is a Chancellor professor in the Operations Research and Industrial Engineering department at the University of California in Berkeley. Professor Adler holds a B.A in Economics and Statistics from the Hebrew University in Israel (1966), a M.Sc. in Operations Research from the Technion in Israel (1967), and a Ph.D. in Operations Research from Stanford (1971). His main research interests are in the areas of Mathematical Programming, Game Theory, and Applied Probability.