Suppose we are given a \$d\$-dimensional polytope, \$P\$, defined by \$n\$ linear inequalities. If \$u\$ and \$v\$ are vertices of \$P\$, we can measure their distance in the underlying graph of \$P\$. How far apart can they be? The Hirsch conjecture posited that the distance from \$u\$ to \$v\$ is at most \$n-d\$. This was disproved by Santos in 2012, though currently the best known upper bounds on the diameter of a polytope are linear in \$n\$ (but exponential in \$d\$), while the best known lower bounds are \$n-d+o(1)\$.
In this talk, we will study a related problem – how far apart can two vertices be in the cocircuit graph of an oriented matroid. The first half of the talk will be spent defining all the words in the previous sentence and building a connection between this problem and diameters of polytopes. In the second half, we will outline our main results, including a diameter bound for oriented matroids that is quadratic in both \$n\$ and \$d\$.
This is joint work with Ilan Adler, Jesús DeLoera, and Zhenyang Zhang.