The linear diameter conjecture for cocircuit graphs of oriented matroids

The conjecture asserts that every cocircuit graph has diameter at most $n-r+2$. It is described as a longstanding folklore problem, but no source found a proof or counterexample to this exact bound.

Known results

• For uniform oriented matroids, equality holds when $n\leq 9$, $r\leq 3$, or $n-r\leq 4$ (Adler, de Loera, Klee, and Zhang, 2020).
• The cases $r\leq 3$ were previously proved by Babson, Finschi, Fukuda, and by Felsner et al.
• It suffices to consider uniform oriented matroids; improved general upper bounds remain larger than $n-r+2$.

2020 construction reaching the bound

Adler, de Loera, Klee, and Zhang exhibited a uniform oriented matroid of rank $21$ on $40$ elements with non-antipodal cocircuits at distance at least $21=n-r+2$. This refutes stronger proposed bounds such as $n-r+1$, but it does not disprove the linear diameter conjecture.

Current status (as of September 2026): The bound $\operatorname{diam}(G^*(\mathcal{M}))\leq n-r+2$ is established in several restricted cases, but remains open in general, with no verified proof or counterexample found.