Cocircuit Graph Diameter Conjecture for Oriented Matroids

Definitions and mathematical statement

Let $M$ be a finite oriented matroid on a ground set $E$, with $|E|=n$ and underlying matroid rank $r$. Write $\mathcal L(M)\subseteq\{0,+,-\}^{E}$ for its covectors. For a sign vector $X$, define its zero set and support by \[ X^0=\{e\in E:X_e=0\},\qquad \operatorname{supp}(X)=E\setminus X^0. \] A cocircuit is a nonzero covector whose support is inclusion-minimal among supports of nonzero covectors. Denote the set of cocircuits by $\mathcal C^*(M)$. For sign vectors $X,Y$, define their separation set by \[ S(X,Y)=\{e\in E:X_e=-Y_e\ne0\}. \] For $r\ge2$, use the following cocircuit graph convention: $G^*(M)$ is the undirected graph with vertex set $\mathcal C^*(M)$, in which distinct vertices $X,Y$ are adjacent precisely when \[ S(X,Y)=\varnothing \quad\text{and}\quad \operatorname{rk}_M(X^0\cap Y^0)=r-2. \] Here $\operatorname{rk}_M$ denotes rank in the underlying matroid. For a nonempty connected graph, distance is the minimum number of edges in a path, and diameter is the maximum distance between two vertices. For a nonempty disconnected graph, take its diameter to be $+\infty$.

The supplied conjecture asks whether, for every oriented matroid $M$ of rank $r$ on $n$ elements, \[ \operatorname{diam}\left(G^*(M)\right)\le n-r+2. \] No uniformity, simplicity, or realizability hypothesis is supplied. The record also gives no lower bound on $r$ and no conventions for cocircuit graphs in ranks zero and one or for an empty graph. Thus the displayed conjecture preserves the supplied quantification, but its intended low-rank scope requires clarification; the explicit graph definition above fixes the interpretation only for $r\ge2$.

Short English statement

The conjecture asks whether any two cocircuits of an oriented matroid on $n$ elements and of rank $r$ can be joined in its cocircuit graph using at most $n-r+2$ edges. The source supplies no additional structural hypotheses, and its intended treatment of ranks zero and one remains unclear. Its open status is supplied dated curation, not an independently verified conclusion.

Sources

• Local UnsolvedMath registry, supplied complete record for permanent ID $30004220$, titled "Cocircuit Graph Diameter Conjecture for Oriented Matroids," source problem code catalogue entry. The record supplies proposed year 2019 and identifies no individual proposer. Its statement status is corrected_verified, described as preserving mathematical content while repairing notation, typography, and sentence structure; this is supplied metadata, not independent mathematical verification.
• Supplied report citation: Geometric, Algebraic, and Topological Combinatorics (2020), Oberwolfach Reports, pp. 2395--2472, DOI 10.4171/owr/2019/39. https://doi.org/10.4171/owr/2019/39. The background identifies Oberwolfach Reports as documentation of mathematical workshops and their open-problem discussions.
• Supplied literature reference: Adler, De Loera, Klee, and Zhang, "cocircuit diameters." https://doi.org/10.37236/9653.
• Supplied literature reference: "Oberwolfach Report 39, oriented matroids." https://doi.org/10.4171/owr/2019/39.
• Literature assessment dated 2026-08-22: the supplied curation labels the conjecture open and states that low-rank, low-corank, and small-ground-set cases are proved, together with quadratic general bounds. This is supplied dated literature triage derived from the OWR curation, not an independently verified assessment. The record requests independent verification of time-sensitive status and cited claims; it does not specify the parameter ranges or precise quadratic bounds.