WorksMathematics
A counterexample to the cocircuit diameter conjecture
Abstract
A rationally realizable uniform rank-41 oriented matroid on 80 elements has cocircuit-graph diameter at least , refuting the general cocircuit diameter conjecture. We build on the rank-21 example of Adler, De Loera, Klee and Zhang, the non-Hirsch polytope of Matschke, Santos and Weibel, Santos's product construction, and the source certification of Allamigeon, Canu and Strub. A count of negative coordinates confines every potentially shorter walk to two affine sections; projection to the product factors then gives the lower bound. Two rational perturbations make the resulting oriented matroid uniform. Lean 4 separately verifies the matrix existence and walk lower bound for a different realizing matrix; the printed perturbations are proved here, not checked in Lean. This work has not yet been reviewed by experts. The proofs, the Lean formalization, the certificate checkers and the text were produced by AI models, working under the author's direction.
2020 Mathematics Subject Classification: 52C40, 05C12, 52B05.
Introduction
Let have rank . Its sign covectors are , , with values in . Its cocircuits are the nonzero covectors of minimal support. Write and for the separation set. When every -row minor of is nonzero, the associated oriented matroid is uniform; every cocircuit has zeros. Its full cocircuit graph has all signed cocircuits as vertices, with distinct adjacent when and . Rational realizability means can be chosen over . Cocircuits are antipodal if , and nonantipodal otherwise. Write for distance in .
Adler, De Loera, Klee and Zhang’s (ADKZ) Conjecture 1 states that every rank- oriented matroid on elements has cocircuit-graph diameter at most [4 Conjecture 1]. Babson, Finschi and Fukuda’s early farthest-pairs question [1 final remarks, pp. 13–14] and Felsner, Gómez, Knauer, Montellano-Ballesteros and Strausz’s Question 4.2 [3] precede ADKZ’s formulation. ADKZ report Fukuda’s personal communication that the bound is folklore. Klee’s report attributes its introduction to Fukuda and Terlaky [13 p. 2425].
Theorem 1. There exists a rationally realizable uniform oriented matroid of rank on elements whose cocircuit graph has diameter at least .
ADKZ state a uniform rank-21 example on 40 elements with nonantipodal cocircuits at distance at least 21 [4 Proposition 8]. Their proof uses the 20-dimensional non-Hirsch polytope of Matschke, Santos and Weibel (MSW), with 40 facets [6 Theorem 1.3], obtained using Santos’s construction [7 Theorem 2.6]. Allamigeon, Canu and Strub (ACS) proved its diameter 21 in Coq [8 §5, PDF p. 12]. We reuse their numerical inequality data and check a new certificate for the designated pair. Product amplification is standard [7 Lemma 6.1 and §6], where Santos cites Klee–Walkup, Proposition 1.3.
We must control walks that leave the product’s nonnegative section. The lifted source matrix is not uniform: rows 5, 7–10 and 27–29 are supported on the first six columns (Appendix § 6). We first perturb it to a uniform rank-21 factor, preserving the pair at distance 21. Two factors give 80 inequalities in rank 41: the product pair is 42 edges apart; the conjectured bound is . To exclude shorter cocircuit walks, Lemma 2 generalizes ADKZ’s count of sign-coordinate changes [4 Lemma 5 and proof of Proposition 8]: a walk of at most 41 edges can visit at most one negative coordinate. Such a walk stays in the union of two sections. A second uniform perturbation preserves these sections; projection to the factors still requires 21 + 21 edges.
A lower bound on walk length
Fix an inequality matrix and put and . Choose a rational linear functional positive on every nonzero vector in these cones. The affine section of a cone is ; positivity makes it bounded (Lemma 4(a)). The sections of and are nonnegative and singly reversed, respectively. A row is tight when equality holds; the tight row labels form the active set. When is uniform and the section is full-dimensional, we identify a section vertex with the cocircuit ; its active set is its zero set (Lemma 3). A -dimensional section is simple if each vertex lies on exactly facets.
Lemma 2. Let be the cocircuit graph of a uniform rank- oriented matroid on elements. Suppose that are complementary -element sets and are positive elsewhere. For a walk of length from to , let be the number of coordinates that are negative at any vertex of the walk. Then
Proof. Adjacent cocircuits have zeros each, sharing . Exactly one zero becomes nonzero and one nonzero becomes zero. All other nonzero entries agree because the separation set is empty. Thus exactly two coordinates change, each by absolute amount one. The complementary endpoint zero sets make every coordinate go from 0 to 1 or from 1 to 0. Its total absolute change is at least one, or at least three if it visits . Summing gives .
For and , the walk uses at most one fixed negative coordinate , so every vertex lies in or . If none is negative, any works.
Lemma 3. Let have rank and be uniform. Let a rational linear functional be positive on every nonzero vector of and every . Suppose each section by is bounded and has dimension . Each section graph is the restriction of to cocircuits satisfying its sign requirements for , or and for for . For every row index , every walk whose negative coordinates are contained in lies in the union of the graphs of the sections of and .
Proof. The zero rows of a cocircuit are independent. Their kernel is a line; choosing the signs selects a ray. Positivity of gives exactly one representative with , and excludes the antipodal ray from that cone. This representative is a section vertex. Conversely, a section vertex needs $r independent tight rows; uniformity forbids more, so its sign vector is a cocircuit. These independent active rows give local coordinates in the -dimensional section, so it is simple. Two vertices sharing tight rows are the endpoints of their common one-dimensional face, and every edge has such endpoints. Conversely, full-graph adjacency between section vertices requires these shared zeros, so gives such a section edge. Separation is empty inside one of these cones; thus its graph is the induced cocircuit subgraph on those vertices. For an adjacent pair with no negative coordinates outside , if either has a negative entry at , the other has a nonpositive entry there: opposite nonzero signs are excluded by adjacency. Both then lie in . Otherwise both lie in . When both signs at vanish, both vertices lie on the shared facet and the edge lies in both graphs. Every walk edge therefore belongs to one of the two section graphs.
The construction
Put , with the rational matrix and functional specified in Appendix § 6. The source certificate [12], detailed in Appendix § 7, gives a simple 20-dimensional and for vertices with active rows 1–20 and 21–40, respectively. The inequality data are poly20dim21.ine in Coq-Polyhedra (Allamigeon, Katz and Strub). ACS attribute the supplied inequalities to Weibel [8 §5, PDF p. 11, footnote 6]; Allamigeon, Id-Sahra and Strub likewise credit MSW for the 20- and 23-dimensional non-Hirsch polytopes they consider [11 §1]. We use the documented attribution for credit; the source file was not compared entrywise with MSW’s table. The proof uses the exact matrix and certificate specified here; the supplement records the source version and comparisons. Clearing each row’s reduced denominators by their least common multiple gives , leaving every sign unchanged. Let have entries : is all positive, and reverses row for . Appendix § 6 gives a rational row vector and weights satisfying
These exact identities, with rank , imply on every nonzero vector of each closed cone: its signed slacks are nonnegative and not all zero.
Lemma 4 (Stability of bounded simple sections). Let and let be finite. Suppose a linear functional is positive on every nonzero vector of
(a) For all in a sufficiently small neighborhood of in , the same positivity holds and the sections are uniformly bounded. (b) For each whose original section has dimension and exactly independent active rows at every vertex, its perturbed section has the same dimension and face lattice, with the same row labels and nonzero signs. For two patterns satisfying these hypotheses, their perturbed sections intersect in the face where all rows on which and differ are tight. This is the continuation of their original common face, and the two continuation maps agree on its vertices and edges.
Proof. Positivity and boundedness. Failure of positivity along would give unit vectors in perturbed cones with ; a convergent subsequence contradicts the original positivity. Unbounded normalized sections similarly give a unit limit in an original cone with . Vertices. For a full-dimensional original section, a point with all inequalities strict remains feasible, preserving dimension. Each original vertex continues uniquely through its nonsingular active-row system and . Every inactive signed slack was strictly positive; by continuity it remains so, giving exactly the original active set. Suppose additional vertices appeared along . Uniform boundedness gives a convergent subsequence with limit . Finiteness of row subsets gives a further subsequence with a fixed set of independent tight rows at the perturbed vertices. These rows need not a priori be independent at . The original bounded face with tight contains by continuity of every signed inequality and tight equation. This nonempty bounded polyhedral face has a vertex . Its active set contains and has the same cardinality , so equals . Thus has rank , and , uniquely determines . For sufficiently small perturbations the system remains nonsingular; the alleged additional vertex is the continuation of .
Faces. Identify each vertex with its unique continuation, retaining its active set and nonzero signs. For a row subset , the face cut out by making tight has precisely the vertices whose active sets contain . The continuation map preserves this vertex set and its emptiness, for each section satisfying the stated dimension and active-row hypotheses. Every face of an inequality polytope has this form and is the convex hull of its vertices. Thus equal faces, and inclusion between faces, are preserved in both directions. This gives a face-lattice bijection, preserving edges and their endpoint pairs.
Common faces. If two patterns differ on , the intersection of their sections is the face obtained by making tight in either section. Every vertex of this face is a vertex of both sections: in a convex decomposition into section points, all signed slacks on are nonnegative and average to zero, so both points lie in the common face. A nontrivial decomposition would contradict its being a vertex there. A row is tight precisely when its linear form is zero, independently of the sign pattern. The active set is thus the same in both sections, has exactly rows, and contains . Its continuation is the unique solution of , in either section. The identifications, full sign vectors and common-face edges consequently agree. Intersecting the neighborhoods for the finitely many sections and vertex systems gives one neighborhood for every .
Set , where has 21 columns. Each 21-row minor is a polynomial in with nonzero Vandermonde leading coefficient, so all are nonzero for sufficiently small rational . Apply Lemma 4 with : stays positive on these 41 cones. Each vertex of has exactly 20 independent tight rows, as the certificate checks. The section of is therefore simple, so Lemma 4 preserves its graph with the active row labels. Let be the resulting uniform matrix, and the unique continuations of . Write for the section graphs of , respectively.
Lemma 5. Each reversed section has dimension 20, and every vertex has exactly 20 independent tight rows.
Proof. All reversed sections are bounded by Lemma 4, applied above with all 41 patterns. (1) Every row is active at or . There the twenty independent active constraints are local coordinates on . Keeping one zero and making the other nineteen positive gives a 19-dimensional face. Thus every row defines a facet of the nonnegative section.
(2) A facet’s affine span in spans a linear hyperplane in . Two rows defining the same facet therefore vanish on the same hyperplane and are proportional, contradicting a nonzero 21-row minor of the uniform matrix . Distinct rows define distinct facets.
(3) At a relative-interior point of facet , any other tight row would vanish on the facet’s affine span: a nonnegative affine form vanishing at an interior point vanishes identically there. This would make its facet equal to facet , since both are facets by (1), contradicting (2). Thus only row is tight. Crossing its hyperplane within makes row negative and all others positive, giving a 20-dimensional reversed section.
(4) At every reversed-section vertex at least twenty independent constraints are tight. Uniformity forbids 21 tight rows, whose common kernel would be zero. Thus exactly twenty rows are tight and independent. ▢
By Lemma 3, , are subgraphs of , identified by sign vectors. Their union is the induced subgraph on the cocircuits satisfying either set of sign inequalities. inherits ’s graph and row labels, giving . Their active labels still partition the 40 facets, so the cocircuits corresponding to have complementary zero sets and are positive elsewhere.
Lemma 6. Every – walk in has length at least 21.
Proof. This is ADKZ’s Proposition 8 count applied to . For a walk of length at most 20, Lemma 2 with gives . Its vertices are nonnegative, so Lemma 3 puts it in , contradicting .
Choose rational coordinates with , so the affine sections lie in . After this rational invertible change of coordinates we may assume that with and , so . The change preserves all sign vectors and nonvanishing maximal minors. In product coordinates , the inequality matrix is
The section of is a product of two 20-dimensional polytopes. Its vertices are pairs of factor sign vectors; each edge moves one factor. For a flip in the first factor, the reversed section graph is . We use only the inclusion
Here is the Cartesian product of graphs. The second-factor case is symmetric.
For the second perturbation, set with and seek with rational sufficiently small.
Lemma 7. For some rational , the matrix is uniform. The functional is positive on every nonzero vector of and all . Their sections by are bounded, have dimension 40, and have the same graphs and common faces as the corresponding sections for , identifying vertices by active rows together with their sign vectors.
Proof. Fix and before choosing . Every factor section has dimension 20, by the construction of for and Lemma 5 for . Uniformity of gives exactly 20 independent active rows at each vertex, with all other signed inequalities strict. All 81 sections (the nonnegative section and one reversal for each of the 80 rows) thus have dimension 40. Fixing makes the two factor blocks independent. Each product-section vertex is a pair of factor-section vertices. The active equations in the and variables form two nonsingular blocks of size 20, giving exactly 40 independent active equations. The remaining signed inequalities are strict. On each product cone the two factor vectors belong to or one and share the coordinate . Positivity of the factor functional forces ; if , both factor vectors vanish. Thus on every nonzero vector of all 81 product cones. Their sections in the common hyperplane are bounded. The product may be nonuniform. For any 41-row set , has degree 41: its top coefficient is the Vandermonde determinant of 41 distinct integers and is nonzero. All finitely many maximal-minor polynomials are therefore nonzero for sufficiently small . Use consisting of the all-positive pattern and each of its 80 single reversals. Lemma 4 applies: the functional remains positive, the sections remain uniformly bounded, and their labeled graphs and shared faces are preserved.
Proof of Theorem 1. Lemma 7 gives a uniform , positivity of , and bounded sections of dimension 40. Thus Lemma 3 applies. In the section of choose the vertices labeled and . Their zero sets are complementary 40-element sets and both are positive elsewhere. Suppose there were a full-graph walk of length between them. Lemmas 2 and 3 confine its vertices and edges to the sections of and one fixed . Lemma 7 transports the walk to , preserving active rows and sign vectors. The common-face clause of Lemma 4(b) makes the two section maps agree on every shared vertex and edge. If the fixed coordinate belongs to the first factor, the resulting walk is in . The first-factor projection lies in and the second in . By Lemma 3 applied to , both and are subgraphs of . Project the whole walk to each factor and delete consecutive repetitions. Each edge moves exactly one factor, so the lengths of the projected walks sum to . Lemma 6 requires at least 21 first-factor edges, and requires at least 21 second-factor edges. Thus , a contradiction. The second-factor case is identical. Every 41-row minor of is nonzero, so its rank is 41. Its real sign covectors give the standard realizable oriented matroid, uniform by these minors and rationally realizable since is rational.
Remark 8. The distance between these two vertices is exactly 42. The two 21-edge paths in , continued to , give the path
in the product section. Lemma 7 preserves its edges after the second perturbation. This gives the upper bound 42, matching the lower bound in the proof of Theorem 1.
Formal verification
The Lean theorem ADKZPricing.Generated.source_frozen_endpoint asserts that there is with every 41-row minor nonzero and real signed cocircuits having complementary 40-element zero sets and positive entries elsewhere, such that no walk of at most 41 edges joins them. This is Theorem 1 for a different matrix from § 3. The walks allow arbitrary signed intermediate cocircuits and repetitions; antipodal sign vectors are distinct vertices.
In the formal definitions, cocircuits are nonzero covectors minimal under conformality: a conformal face of has for every . Adjacency is defined by composition, if and otherwise: for distinct , the compositions and must agree and be a covector having exactly as cocircuit conformal faces. In the uniform case, Lean proves that conformality-minimality agrees with support-minimality and that this adjacency agrees with § 1: empty separation set and 39 common zeros. Thus the formal walk bound has the stated full-graph meaning; the passage from real matrix sign covectors to the standard realizable oriented matroid is the usual mathematical interpretation.
Lean uses a different positive functional for the same and the same product-and-perturb strategy. Its rational perturbations are chosen nonconstructively; the endpoint theorem specifies existentially, without printing its entries. The printed Vandermonde perturbations are not checked in Lean; their proofs and Remark 8’s upper bound are written. The formal statement, axioms and reproduction instructions are given in [12].
Further questions
The diameter of the full cocircuit graph of this example is unknown. What is the least counterexample rank? What sharp bound replaces ?
Fukuda’s linear-bound question remains [5 §3.7.2, PDF p. 16]; see also [2 Open Problem 5].
An exact positive-functional certificate
This appendix specifies the source matrix and a positive functional for the cones obtained by reversing at most one row. Row and column labels are one-based: , ; denotes the nonnegative cone and reverses row .
The integer source matrix
Let denote the th coordinate row of and let be row of . For the rows in the following table set
| 1 | 1 | 0 | 0 | 21 | -7 | |
| 2 | 1 | 0 | 0 | 16 | -15 | |
| 3 | 1 | 0 | 0 | 0 | -32 | |
| 4 | 1 | 0 | 0 | -16 | -15 | |
| 5 | 1 | 0 | 0 | -21 | -7 | 0 |
| 6 | 1 | 0 | 0 | -20 | -4 | |
| 7 | 1 | 0 | 0 | 0 | 32 | 0 |
| 8 | 1 | 0 | 0 | 20 | -4 | 0 |
| 9 | 100 | 3 | -2 | 0 | -3000 | 0 |
| 10 | 100 | -3 | -2 | 0 | 3000 | 0 |
| 11 | 2000 | -3 | 7 | 0 | 63600 | |
| 21 | 1 | 30 | 0 | 0 | 0 | |
| 22 | 1 | 4 | -15 | 0 | 0 | |
| 23 | 2 | 0 | -33 | 0 | 0 | |
| 24 | 1 | -1 | -16 | 0 | 0 | |
| 25 | 2 | -55 | 0 | 0 | 0 | |
| 26 | 1 | -17 | 18 | 0 | 0 | |
| 27 | 1 | 0 | 38 | 0 | 0 | 0 |
| 28 | 1 | 22 | 17 | 0 | 0 | 0 |
| 29 | 5 | -50 | 0 | 1 | -1 | 0 |
| 30 | 100 | 2999 | 0 | -12 | -20 | |
| 31 | 10000 | 299999 | 0 | 0 | 100 | |
| 32 | 20000 | -549000 | 0 | 4 | 25 |
Table 1.
The remaining seventeen rows are specified by two triangular recipes. Define
Then
Likewise define
Then
Empty sums are zero, and all entries not specified by these recipes are zero. These recipes give exactly the integer matrix obtained by clearing each source row’s reduced denominators by their least common multiple.
The functional and weights
Set , where the integers are
| 1 | 7 889 496 505 278 816 | 8 | 16 770 653 889 890 | 15 | 11 008 963 417 |
| 2 | -788 643 250 921 389 998 | 9 | 16 773 144 135 505 | 16 | 193 944 140 058 |
| 3 | -322 873 814 | 10 | 2 918 818 204 673 914 | 17 | 570 600 902 642 |
| 4 | 73 889 176 985 687 161 | 11 | 2 039 103 229 854 373 | 18 | 574 335 730 279 |
| 5 | 0 | 12 | 1 964 406 684 567 592 | 19 | 186 741 363 964 |
| 6 | -8 399 586 269 177 | 13 | 2 477 284 371 671 404 | 20 | 112 044 818 677 |
| 7 | 16 778 123 544 418 | 14 | 2 402 587 826 384 623 | 21 | 373 482 727 181 |
Table 2.
Let for every ; for let and for . For each , specify an increasing list as follows:
In the table, . Each displayed comma-separated entry denotes a set, and a multi-label row assigns the same sets to every listed .
| (delete from ) | (add to ) | |
| 0, 1 | ||
| 2 | 1 | |
| 3 | 2, 19, 25 | 8, 12, 34 |
| 5 | 2, 5, 7, 38 | 1, 6, 12, 34 |
| 7 | 2, 7 | 1, 11 |
| 9 | 5, 7, 33, 38, 39 | 1, 4, 6, 11, 12 |
| 12 | 2, 5, 27 | 3, 4, 26 |
| 13 | 2, 5, 13, 16, 21, 25 | 4, 6, 12, 28, 30, 34 |
| 14 | 2, 14, 25, 27 | 3, 12, 28, 32 |
| 15 | 2, 5, 15, 21, 25, 27 | 4, 12, 26, 28, 31, 34 |
| 16 | 2, 5, 16, 21, 25 | 3, 12, 30, 31, 34 |
| 17 | 2, 5, 17, 18 | 3, 6, 22, 26 |
| 18 | 2, 5, 13, 18, 19 | 3, 4, 12, 22, 26 |
| 19 | 2, 5, 19, 25, 27 | 3, 6, 12, 26, 34 |
| 20 | 2, 5, 16, 18, 20 | 3, 4, 12, 22, 24 |
| 21 | 2, 5, 13, 15, 21, 25 | 1, 6, 12, 22, 32, 34 |
| 25 | 5, 7, 25, 33, 38, 39 | 1, 4, 6, 12, 32, 34 |
| 27 | 2, 5, 19, 27 | 1, 6, 26, 34 |
| 33 | 2, 5, 7, 25, 33, 37 | 1, 4, 8, 11, 12, 24 |
| 34, 38, 39 | 5, 33, 38, 39 | 1, 4, 6, 12 |
| 35 | 2, 5, 7, 33, 35, 38 | 1, 3, 6, 8, 11, 12 |
| 36 | 5, 36, 39 | 1, 6, 12 |
| 37 | 5, 36, 37 | 3, 4, 12 |
| 40 | 2, 35, 38, 40 | 1, 3, 6, 12 |
Table 3.
Write and define
Let mean replace column of by , and put
Evaluating these integer determinants exactly gives
Thus all weights are at least 1 (basis weights exceed 9), and Cramer’s rule gives for every . Also gives . If has all signed slacks , full column rank makes at least one slack positive, so . Every datum needed for these finite checks is printed in this appendix. An exact checker of these formulas is included in [12].
For example, the first row is . The supplement’s exact checker reconstructs every entry from these recipes, compares them with the rational inequality data, and verifies the displayed weight identities. The positive functional used in Lean differs from the one printed here.
Completeness of the vertex certificate
The following local certificate criterion explains the completeness fact used in § 3. The large finite list is in [12]; completeness is a consequence, not a premise supplied by the list. The labeled pair, potential, path and local source data are supplied only in the supplement and checked there; their large tables are not printed here. The pair has the complementary-zero-set form used in [4 proof of Proposition 8].
Lemma 9. Let be full-dimensional. Suppose a nonempty finite set is given, each having exactly tight rows, whose matrix is invertible. For each of these rows , suppose a point satisfies
where is the th coordinate vector. Then is the complete vertex set, is simple, and its neighbors at are precisely the points .
Proof. For a linear objective , choose maximizing on this finite set. For every , the vector has nonnegative coordinates and
Since , this proves : the list contains a global maximizer for every linear objective.
Let be any vertex and choose independent tight rows there. The objective is maximized precisely where all these rows are tight, because their slacks are nonnegative. Its unique feasible maximizer is . A listed maximizer must therefore equal . Conversely each listed point is a vertex by its nonsingular tight system, so the list is complete and every vertex has exactly tight rows. Each such row defines a distinct facet locally. Releasing one row while retaining the other defines an edge. The distinct vertices lie on that one-dimensional face and hence are its two endpoints. Every edge at a simple vertex arises this way.
Here are the exact formal interfaces for these inputs, in the Lean development linked below the title; all names have prefix ADKZPricing. For the literal matrix , Generated.source_valid proves IntegerSourceValid for the supplied 36,425 rays, their 20-element bases and their neighbors. Its field hypotheses are checked finite arithmetic: positive normalizing coordinates, feasible rays, injective and exact active labels, and a neighbor retaining every basis row except the released one. The resulting Generated.sourceCertificate is a SourceVertexCertificate. For this certificate, the theorems SourceVertexCertificate.covers_active_labels, SourceVertexCertificate.active_count and SourceVertexCertificate.basis_nonsingular give
where is the supplied list, its ray normalized by , and its tight-row set. In particular, is simple. The normalization changes only the scale of each ray, preserving vertices, facets and their incidence; Lemma 9 is the corresponding written local-to-global argument.
The theorem msw_integral_real_vertices verifies the endpoints with tight rows 1–20 and 21–40. The theorems Generated.source_local_potential and Generated.source_specified_gap verify the local potential inequalities and endpoint gap at least 21. Applying SourceVertexCertificate.potential_edge and SourceVertexCertificate.specified_distance_lower_bound therefore gives a 1-Lipschitz potential on every geometric edge and , with no assumed completeness or distance premise. The separate exact checkers check_fraction.py and check_rational.py (folder checks of [12]) verify the supplied 21-edge path, giving ; this upper bound is not a Lean distance-equality theorem. These source facts and Appendix § 6’s identities are the complete computational input to the written construction. No enumeration of the final 80-element cocircuit graph is used.
Earlier farthest-pair questions
The diameter conjecture is related to earlier questions about which pairs of cocircuits are farthest apart; we distinguish those questions here. For uniform oriented matroids, Babson, Finschi and Fukuda prove antipodal distance [1 Lemma 2] and equality exactly for antipodal pairs in uniform ranks two and three [1 Lemma 6]. ADKZ answer Finschi’s Open Problem 2 and refute the equality half of [3 Question 4.2] with their nonantipodal example [4 Proposition 8 and preceding paragraph]. Their proof already uses a pair at distance 21 in the source polytope; here an explicit path gives equality for the source matrix specified in Appendix § 6. Finschi’s Open Problem 4 asks whether a uniform cocircuit graph can have an antipodal pair whose distance differs from the diameter, or a nonantipodal pair attaining the diameter [2 p. 90]; this is the farthest-pairs question in [1 final remarks, pp. 13–14]. ADKZ’s lower-bound argument answers it affirmatively once the source example is made uniform, as in Lemmas 5–6: if the diameter is 21, the nonantipodal pair attains it; if larger, antipodal pairs are not farthest. Here every antipodal pair is shorter than some nonantipodal pair. This refutes the diameter half of Question 4.2 and ADKZ’s Conjecture 1.
A crabbed path from to has and at every vertex , where and . ADKZ exhibit a realizable rank-four example on nine elements in which a shortest path is shorter than every crabbed path [4 Theorem 9].
Adjacent work concerns e-positive circuit graphs of oriented matroid polyhedra and embracing exchange distance (Bérczi, Knauer, Montajano and Nádor [9 Corollary 1.4 and Definition 2.1]), smaller non-Hirsch polytopes (Świrszcz and collaborators [10 §4.1]), and polyhedron certification (Allamigeon, Id-Sahra and Strub [11 abstract and §1]).
References
- [1]E. Babson, L. Finschi and K. Fukuda, Cocircuit graphs and efficient orientation reconstruction in oriented matroids, European Journal of Combinatorics 22 (2001), 587–600. doi:10.1006/eujc.2001.0481. Statement locators refer to the May 4, 2001 author version.DOI
- [2]L. Finschi, A graph theoretical approach for reconstruction and generation of oriented matroids, doctoral thesis, ETH Zürich, 2001. doi:10.3929/ethz-a-004255224. Author copy.DOI
- [3]S. Felsner, R. Gómez, K. Knauer, J. J. Montellano-Ballesteros and R. Strauß, Cubic time recognition of cocircuit graphs of uniform oriented matroids, European Journal of Combinatorics 32 (2011), 60–66. doi:10.1016/j.ejc.2010.07.012. arXiv:1001.3534v1 (2010; statement numbering).DOI
- [4]I. Adler, J. A. De Loera, S. Klee and Z. Zhang, Diameters of cocircuit graphs of oriented matroids: an update, Electronic Journal of Combinatorics 28 (2021), no. 4, P4.40. doi:10.37236/9653.DOI
- [5]G. M. Ziegler, L. Anderson and K. Knauer, Oriented matroids today, Electronic Journal of Combinatorics, Dynamic Survey DS4, version 4, April 16, 2024. Version 4.
- [6]B. Matschke, F. Santos and C. Weibel, The width of five-dimensional prismatoids, Proceedings of the London Mathematical Society (3) 110 (2015), 647–672. doi:10.1112/plms/pdu064. arXiv:1202.4701v2 (statement numbering).DOI
- [7]F. Santos, A counterexample to the Hirsch conjecture, Annals of Mathematics 176 (2012), 383–412. doi:10.4007/annals.2012.176.1.7. Statement numbering refers to the Annals version.DOI
- [8]X. Allamigeon, Q. Canu and P.-Y. Strub, A Formal Disproof of the Hirsch Conjecture, Proceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs (2023), 17–29. doi:10.1145/3573105.3575678. arXiv:2301.04060v1 (statement and page numbering).DOI
- [9]K. Bérczi, K. Knauer, L. P. Montejano and B. Nádor, Embracing exchange sequences and oriented matroid polyhedron diameter, arXiv:2606.19573v2 (2026).arxiv.org/abs/2606.19573
- [10]G. Świrszcz, A. Z. Wagner, G. Williamson, S. Blackwell, B. Georgiev, A. Davies, A. Eslami, S. Racanière, T. Weber and P. Kohli, Advancing Geometry with AI: Multi-agent Generation of Polytopes, arXiv:2502.05199v1 (2025).arxiv.org/abs/2502.05199
- [11]X. Allamigeon, Y. Id-Sahra and P.-Y. Strub, Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration, arXiv:2610.11913v1 (2026).arxiv.org/abs/2610.11913
- [12]P. Graham, Supplementary material for a counterexample to the cocircuit diameter conjecture, version 1 (2026). Supplementary data and Lean formalization.DOI
- [13]S. Klee, Diameter bounds on cocircuit graphs of oriented matroids, Oberwolfach Report 39/2019, pp. 2424–2426 (joint work with I. Adler, J. A. De Loera and Z. Zhang). Report.