betaFeedback

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 42>41=n−r+242>41=n-r+2, 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 A∈Rn×rA \in\mathbb{R}^{n \times r} have rank rr. Its sign covectors are sgn⁡(Ax)\operatorname{sgn}(Ax), x∈Rrx \in\mathbb{R}^{r}, with values in {−1,0,1}n\{-1,0,1\}^{n}. Its cocircuits are the nonzero covectors of minimal support. Write X0={i:Xi=0}X^{0} = \{i : X_i = 0\} and S(X,Y)={i:Xi=−Yi≠0}S(X,Y) = \{i : X_i = -Y_i \ne0\} for the separation set. When every rr-row minor of AA is nonzero, the associated oriented matroid is uniform; every cocircuit has r−1r-1 zeros. Its full cocircuit graph G∗(A)G^{*}(A) has all signed cocircuits as vertices, with distinct X,YX,Y adjacent when S(X,Y)=∅S(X,Y) = \varnothing and ∣X0∩Y0∣=r−2|X^{0} \cap Y^{0}| = r-2. Rational realizability means AA can be chosen over Q\mathbb{Q}. Cocircuits X,YX,Y are antipodal if Y=−XY=-X, and nonantipodal otherwise. Write dHd_H for distance in HH.

Adler, De Loera, Klee and Zhang’s (ADKZ) Conjecture 1 states that every rank-rr oriented matroid on nn elements has cocircuit-graph diameter at most n−r+2n-r+2 [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 4141 on 8080 elements whose cocircuit graph has diameter at least 42>41=80−41+242 > 41 = 80 - 41 + 2.

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 M0M_0 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 80−41+2=4180 - 41 + 2 = 41. 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 M∈Rn×rM \in\mathbb{R}^{n \times r} and put C0(M)={z:Mz≥0}C_0(M) = \{z : Mz \ge0\} and Ce(M)={z:(Mz)e≤0,(Mz)i≥0 (i≠e)}C_e(M) = \{z : (Mz)_e \le0, (Mz)_i \ge0\ (i \ne e)\}. Choose a rational linear functional cc positive on every nonzero vector in these cones. The affine section of a cone CC is C∩{c(z)=1}C \cap\{c(z) = 1\}; positivity makes it bounded (Lemma 4(a)). The sections of C0C_0 and CeC_e are nonnegative and singly reversed, respectively. A row is tight when equality holds; the tight row labels form the active set. When MM is uniform and the section is full-dimensional, we identify a section vertex zz with the cocircuit sgn⁡(Mz)\operatorname{sgn}(Mz); its active set is its zero set (Lemma 3). A dd-dimensional section is simple if each vertex lies on exactly dd facets.

Lemma 2. Let G∗G^* be the cocircuit graph of a uniform rank-(d+1)(d + 1) oriented matroid on 2d2d elements. Suppose that X0,Y0X^0, Y^0 are complementary dd-element sets and X,YX, Y are positive elsewhere. For a walk of length LL from XX to YY, let kk be the number of coordinates that are negative at any vertex of the walk. Then

2d+2k≤2L.2d + 2k \le2L.

Proof. Adjacent cocircuits have dd zeros each, sharing d−1d - 1. 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 −1-1. Summing gives 2d+2k≤2L2d + 2k \le2L. □\square

For d=40d = 40 and L≤41L \le41, the walk uses at most one fixed negative coordinate ee, so every vertex lies in C0C_0 or CeC_e. If none is negative, any ee works.

Lemma 3. Let M∈Qn×rM \in\mathbb{Q}^{n \times r} have rank r≥2r \ge2 and be uniform. Let a rational linear functional cc be positive on every nonzero vector of C0(M)C_0(M) and every Ce(M)C_e(M). Suppose each section by c(z)=1c(z) = 1 is bounded and has dimension r−1r - 1. Each section graph is the restriction of G∗(M)G^*(M) to cocircuits satisfying its sign requirements Xi≥0X_i \ge0 for C0C_0, or Xe≤0X_e \le0 and Xi≥0X_i \ge0 for i≠ei \ne e for CeC_e. For every row index ee, every walk whose negative coordinates are contained in {e}\{e\} lies in the union of the graphs of the sections of C0(M)C_0(M) and Ce(M)C_e(M).

Proof. The r−1r - 1 zero rows of a cocircuit are independent. Their kernel is a line; choosing the signs selects a ray. Positivity of cc gives exactly one representative with c(z)=1c(z) = 1, and excludes the antipodal ray from that cone. This representative is a section vertex. Conversely, a section vertex needs $r 11 independent tight rows; uniformity forbids more, so its sign vector is a cocircuit. These r−1r-1 independent active rows give local coordinates in the (r−1)(r-1)-dimensional section, so it is simple. Two vertices sharing r−2r-2 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 r−2r-2 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 ee, if either has a negative entry at ee, the other has a nonpositive entry there: opposite nonzero signs are excluded by adjacency. Both then lie in CeC_e. Otherwise both lie in C0C_0. When both signs at ee 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 P=C0(M0)∩{z:c(z)=1}P=C_0(M_0)\cap\{z:c(z)=1\}, with the rational matrix M0M_0 and functional cc specified in Appendix § 6. The source certificate [12], detailed in Appendix § 7, gives a simple 20-dimensional PP and dP(u,v)=21d_P(u,v)=21 for vertices u,vu,v 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 M0∈Z40×21M_0\in\mathbb{Z}^{40\times21}, leaving every sign unchanged. Let σe∈{−1,1}40\sigma_e\in\{-1,1\}^{40} have entries σe,i\sigma_{e,i}: σ0\sigma_0 is all positive, and σe\sigma_e reverses row ee for e>0e>0. Appendix § 6 gives a rational row vector cc and weights λe,i≥1\lambda_{e,i}\ge1 satisfying

c=∑i=140λe,iσe,i(M0)i,(0≤e≤40).c=\sum_{i=1}^{40}\lambda_{e,i}\sigma_{e,i}(M_0)_i,\qquad(0\le e\le40).

These exact identities, with rank M0=21M_0=21, imply c(z)>0c(z)>0 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 M∈Rn×rM\in\mathbb{R}^{n\times r} and let Σ⊆{−1,1}n\Sigma\subseteq\{-1,1\}^n be finite. Suppose a linear functional cc is positive on every nonzero vector of

Cσ(M)={z:σi(Mz)i≥0 for all i},σ∈Σ.C_\sigma(M)=\{z:\sigma_i(Mz)_i\ge0\text{ for all }i\},\qquad\sigma\in\Sigma.

(a) For all M′M' in a sufficiently small neighborhood of MM in Rn×r\mathbb{R}^{n\times r}, the same positivity holds and the sections Cσ(M′)∩{c=1}C_\sigma(M')\cap\{c=1\} are uniformly bounded. (b) For each σ\sigma whose original section has dimension r−1r-1 and exactly r−1r-1 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 σ,σ′\sigma,\sigma' satisfying these hypotheses, their perturbed sections intersect in the face where all rows on which σ\sigma and σ′\sigma' 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 M′→MM'\to M would give unit vectors in perturbed cones with c≤0c\le0; a convergent subsequence contradicts the original positivity. Unbounded normalized sections similarly give a unit limit in an original cone with c=0c=0. 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 c=1c=1. Every inactive signed slack was strictly positive; by continuity it remains so, giving exactly the original active set. Suppose additional vertices appeared along M′→MM' \to M. Uniform boundedness gives a convergent subsequence with limit zz. Finiteness of row subsets gives a further subsequence with a fixed set II of r−1r-1 independent tight rows at the perturbed vertices. These rows need not a priori be independent at MM. The original bounded face with II tight contains zz by continuity of every signed inequality and tight equation. This nonempty bounded polyhedral face has a vertex ww. Its active set contains II and has the same cardinality r−1r-1, so equals II. Thus MIM_I has rank r−1r-1, and MIz=0M_I z = 0, c(z)=1c(z) = 1 uniquely determines ww. For sufficiently small perturbations the system remains nonsingular; the alleged additional vertex is the continuation of ww.

Faces. Identify each vertex with its unique continuation, retaining its active set and nonzero signs. For a row subset I0I_0, the face cut out by making I0I_0 tight has precisely the vertices whose active sets contain I0I_0. 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 I0I_0, the intersection of their sections is the face obtained by making I0I_0 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 I0I_0 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 II is thus the same in both sections, has exactly r−1r-1 rows, and contains I0I_0. Its continuation is the unique solution of MI′z=0M'_I z = 0, c(z)=1c(z) = 1 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 σ∈Σ\sigma\in\Sigma.

Set F=M0+εJF = M_0 + \varepsilon J, where Jij=(i+1)j−1J_{ij} = (i + 1)^{j-1} has 21 columns. Each 21-row minor is a polynomial in ε\varepsilon with nonzero Vandermonde leading coefficient, so all are nonzero for sufficiently small rational ε>0\varepsilon> 0. Apply Lemma 4 with Σ={σ0,σ1,…,σ40}\Sigma= \{\sigma_0, \sigma_1, \ldots, \sigma_{40}\}: cc stays positive on these 41 cones. Each vertex of PP has exactly 20 independent tight rows, as the certificate checks. The section PP of C0(M0)C_0(M_0) is therefore simple, so Lemma 4 preserves its graph with the active row labels. Let F∈Q40×21F \in\mathbb{Q}^{40 \times21} be the resulting uniform matrix, and U,VU,V the unique continuations of u,vu,v. Write H0,HeH_0,H_e for the section graphs of C0(F),Ce(F)C_0(F),C_e(F), respectively.

Lemma 5. Each reversed section Ce(F)∩{c=1}C_e(F) \cap\{c = 1\} 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 UU or VV. There the twenty independent active constraints are local coordinates on c=1c = 1. 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 c=1c = 1 spans a linear hyperplane in R21\mathbb{R}^{21}. 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 FF. Distinct rows define distinct facets.

(3) At a relative-interior point of facet ee, 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 ee, since both are facets by (1), contradicting (2). Thus only row ee is tight. Crossing its hyperplane within c=1c = 1 makes row ee 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, H0H_0, HeH_e are subgraphs of G∗(F)G^*(F), identified by sign vectors. Their union is the induced subgraph on the cocircuits satisfying either set of sign inequalities. H0H_0 inherits PP’s graph and row labels, giving dH0(U,V)=21d_{H_0}(U,V)=21. Their active labels still partition the 40 facets, so the cocircuits corresponding to U,VU,V have complementary zero sets and are positive elsewhere.

Lemma 6. Every UU–VV walk in G∗(F)G^*(F) has length at least 21.

Proof. This is ADKZ’s Proposition 8 count applied to FF. For a walk of length at most 20, Lemma 2 with d=20d=20 gives k=0k=0. Its vertices are nonnegative, so Lemma 3 puts it in H0H_0, contradicting dH0(U,V)=21d_{H_0}(U,V)=21.

Choose rational coordinates (s,x)∈R×R20(s,x)\in\mathbb{R}\times\mathbb{R}^{20} with s=c(z)s=c(z), so the affine sections lie in s=1s=1. After this rational invertible change of coordinates we may assume that F=(β R)F=(\beta\ R) with β∈Q40\beta\in\mathbb{Q}^{40} and R∈Q40×20R\in\mathbb{Q}^{40\times20}, so F(s,x)=βs+RxF(s,x)=\beta s+Rx. The change preserves all sign vectors and nonvanishing maximal minors. In product coordinates (s,x,y)(s,x,y), the inequality matrix is

B=(βR0β0R)∈Q80×41.B=\begin{pmatrix} \beta& R & 0\\ \beta& 0 & R \end{pmatrix}\in\mathbb{Q}^{80\times41}.

The section of C0(B)C_0(B) 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 He□H0H_e\square H_0. We use only the inclusion

(H0□H0)∪(He□H0)⊆(H0∪He)□H0.(H_0\square H_0)\cup(H_e\square H_0)\subseteq(H_0\cup H_e)\square H_0.

Here □\square is the Cartesian product of graphs. The second-factor case is symmetric.

For the second perturbation, set W∈Q80×41W\in\mathbb{Q}^{80\times41} with Wij=(i+1)j−1W_{ij}=(i+1)^{j-1} and seek A=B+δWA=B+\delta W with rational δ>0\delta>0 sufficiently small.

Lemma 7. For some rational δ>0\delta>0, the matrix A=B+δWA=B+\delta W is uniform. The functional ss is positive on every nonzero vector of C0(A)C_0(A) and all Ce(A)C_e(A). Their sections by s=1s=1 are bounded, have dimension 40, and have the same graphs and common faces as the corresponding sections for BB, identifying vertices by active rows together with their sign vectors.

Proof. Fix FF and ss before choosing δ\delta. Every factor section has dimension 20, by the construction of PP for H0H_0 and Lemma 5 for HeH_e. Uniformity of FF 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 s=1s=1 makes the two factor blocks independent. Each product-section vertex is a pair of factor-section vertices. The active equations in the xx and yy 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 C0(F)C_0(F) or one Ce(F)C_e(F) and share the coordinate ss. Positivity of the factor functional forces s≥0s\geq0; if s=0s=0, both factor vectors vanish. Thus s>0s>0 on every nonzero vector of all 81 product cones. Their sections in the common hyperplane s=1s=1 are bounded. The product may be nonuniform. For any 41-row set II, det⁡(BI+δWI)\det(B_I+\delta W_I) has degree 41: its top coefficient det⁡WI\det W_I is the Vandermonde determinant of 41 distinct integers and is nonzero. All finitely many maximal-minor polynomials are therefore nonzero for sufficiently small δ>0\delta>0. Use Σ\Sigma consisting of the all-positive pattern and each of its 80 single reversals. Lemma 4 applies: the functional ss 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 AA, positivity of ss, and bounded sections of dimension 40. Thus Lemma 3 applies. In the section of C0(A)C_0(A) choose the vertices labeled (U,U)(U,U) and (V,V)(V,V). Their zero sets are complementary 40-element sets and both are positive elsewhere. Suppose there were a full-graph walk of length L≤41L \le41 between them. Lemmas 2 and 3 confine its vertices and edges to the sections of C0(A)C_0(A) and one fixed Ce(A)C_e(A). Lemma 7 transports the walk to BB, 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 ee belongs to the first factor, the resulting walk is in (H0∪He)□H0(H_0 \cup H_e)\mathbin{\Box}H_0. The first-factor projection lies in H0∪HeH_0 \cup H_e and the second in H0H_0. By Lemma 3 applied to FF, both H0H_0 and HeH_e are subgraphs of G∗(F)G^*(F). 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 LL. Lemma 6 requires at least 21 first-factor edges, and dH0(U,V)=21d_{H_0}(U,V)=21 requires at least 21 second-factor edges. Thus L≥42L \ge42, a contradiction. The second-factor case is identical. Every 41-row minor of AA 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 AA is rational.

Remark 8. The distance between these two vertices is exactly 42. The two 21-edge paths in PP, continued to H0H_0, give the path

(U,U),…,(V,U),…,(V,V)(U,U),\ldots,(V,U),\ldots,(V,V)

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 A′∈Q80×41A' \in\mathbb{Q}^{80 \times41} with every 41-row minor nonzero and real signed cocircuits X,YX,Y 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 ZZ of XX has Zi∈{0,Xi}Z_i \in\{0,X_i\} for every ii. Adjacency is defined by composition, (X∘Y)i=Xi(X \circ Y)_i = X_i if Xi≠0X_i \ne0 and YiY_i otherwise: for distinct X,YX,Y, the compositions X∘YX \circ Y and Y∘XY \circ X must agree and be a covector having exactly X,YX,Y 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 M0M_0 and the same product-and-perturb strategy. Its rational perturbations are chosen nonconstructively; the endpoint theorem specifies A′A' 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 n−r+2n-r+2?

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 M0M_0 and a positive functional for the cones obtained by reversing at most one row. Row and column labels are one-based: 1≤i≤401 \le i \le40, 1≤j≤211 \le j \le21; e=0e=0 denotes the nonnegative cone and e=1,…,40e=1,\ldots,40 reverses row ee.

The integer source matrix

Let uju_j denote the jjth coordinate row of Z21\mathbb{Z}^{21} and let mim_i be row ii of M0M_0. For the rows in the following table set

mi=si(u1+100ηiu2)+aiu3+biu4+piu5+qiu6+Ti,ηi={1i≤20,−1i≥21.m_i=s_i(u_1+100\eta_i u_2)+a_i u_3+b_i u_4+p_i u_5+q_i u_6+T_i,\qquad \eta_i=\begin{cases} 1 & i\le20,\\ -1 & i\ge21. \end{cases}
iisis_iaia_ibib_ipip_iqiq_iTiT_i
110021-7u17+u18u_{17}+u_{18}
210016-15u18+u19u_{18}+u_{19}
31000-32u19+u20u_{19}+u_{20}
4100-16-15u20+u21u_{20}+u_{21}
5100-21-70
6100-20-4u21u_{21}
71000320
810020-40
91003-20-30000
10100-3-2030000
112000-370636002000u162000u_{16}
21130000u9+u10u_9+u_{10}
2214-1500u10+u11u_{10}+u_{11}
2320-33002u11+2u122u_{11}+2u_{12}
241-1-1600u12+u13u_{12}+u_{13}
252-550002u13+2u142u_{13}+2u_{14}
261-171800u14u_{14}
271038000
2812217000
295-5001-10
3010029990-12-20100u9100u_9
31100002999990010010000u810000u_8
3220000-549000042520000u720000u_7

Table 1.

The remaining seventeen rows are specified by two triangular recipes. Define

α=2000u1+200000u2+3u3+7u4−63600u6+2000u15,\alpha=2000u_1+200000u_2+3u_3+7u_4-63600u_6+2000u_{15},
(t7,…,t14)=2(1010,1010,1010,1013,1014,1014,1014,1014).(t_7,\ldots,t_{14})=2(10^{10},10^{10},10^{10},10^{13},10^{14},10^{14},10^{14},10^{14}).

Then

m12=α+∑k=714tkuk,mj+6=α+∑k=7j−1tkuk−tjuj(7≤j≤14).m_{12}=\alpha+\sum_{k=7}^{14}t_k u_k,\qquad m_{j+6}=\alpha+\sum_{k=7}^{j-1}t_k u_k-t_j u_j\quad(7\le j\le14).

Likewise define

γ=2000u1−200000u2−54000u3+4u5−25u6,\gamma=2000u_1-200000u_2-54000u_3+4u_5-25u_6,
(h15,…,h21)=2(108,1010,1010,1010,1011,1011,1012).(h_{15},\ldots,h_{21})=2(10^8,10^{10},10^{10},10^{10},10^{11},10^{11},10^{12}).

Then

m33=γ+∑k=1521hkuk,mj+19=γ+∑k=15j−1hkuk−hjuj(15≤j≤21).m_{33}=\gamma+\sum_{k=15}^{21}h_k u_k,\qquad m_{j+19}=\gamma+\sum_{k=15}^{j-1}h_k u_k-h_j u_j\quad(15\le j\le21).

Empty sums are zero, and all entries not specified by these recipes are zero. These recipes give exactly the 40×2140 \times21 integer matrix obtained by clearing each source row’s reduced denominators by their least common multiple.

The functional and weights

Set c(z)=40000∑j=121vjzjc(z)=40000\sum_{j=1}^{21}v_jz_j, where the integers vjv_j are

jjvjv_jjjvjv_jjjvjv_j
17 889 496 505 278 816816 770 653 889 8901511 008 963 417
2-788 643 250 921 389 998916 773 144 135 50516193 944 140 058
3-322 873 814102 918 818 204 673 91417570 600 902 642
473 889 176 985 687 161112 039 103 229 854 37318574 335 730 279
50121 964 406 684 567 59219186 741 363 964
6-8 399 586 269 177132 477 284 371 671 40420112 044 818 677
716 778 123 544 418142 402 587 826 384 62321373 482 727 181

Table 2.

Let σ0,i=1\sigma_{0,i}=1 for every ii; for 1≤e≤401\le e\le40 let σe,e=−1\sigma_{e,e}=-1 and σe,i=1\sigma_{e,i}=1 for i≠ei\ne e. For each ee, specify an increasing list Be=(ℓ1,…,ℓ21)B_e=(\ell_1,\ldots,\ell_{21}) as follows:

K={2,5,7,13,14,15,16,17,18,19,20,21,25,27,33,35,36,37,38,39,40},K=\{2,5,7,13,14,15,16,17,18,19,20,21,25,27,33,35,36,37,38,39,40\},
Be=sort⁡((K∖Re)∪Se).B_e=\operatorname{sort}((K\setminus R_e)\cup S_e).

In the table, D={2,4,6,8,10,11,22,23,24,26,28,29,30,31,32}\mathcal{D}=\{2,4,6,8,10,11,22,23,24,26,28,29,30,31,32\}. Each displayed comma-separated entry denotes a set, and a multi-label row assigns the same sets to every listed ee.

eeReR_e (delete from KK)SeS_e (add to KK)
0, 1∅\varnothing∅\varnothing
D\mathcal{D}21
32, 19, 258, 12, 34
52, 5, 7, 381, 6, 12, 34
72, 71, 11
95, 7, 33, 38, 391, 4, 6, 11, 12
122, 5, 273, 4, 26
132, 5, 13, 16, 21, 254, 6, 12, 28, 30, 34
142, 14, 25, 273, 12, 28, 32
152, 5, 15, 21, 25, 274, 12, 26, 28, 31, 34
162, 5, 16, 21, 253, 12, 30, 31, 34
172, 5, 17, 183, 6, 22, 26
182, 5, 13, 18, 193, 4, 12, 22, 26
192, 5, 19, 25, 273, 6, 12, 26, 34
202, 5, 16, 18, 203, 4, 12, 22, 24
212, 5, 13, 15, 21, 251, 6, 12, 22, 32, 34
255, 7, 25, 33, 38, 391, 4, 6, 12, 32, 34
272, 5, 19, 271, 6, 26, 34
332, 5, 7, 25, 33, 371, 4, 8, 11, 12, 24
34, 38, 395, 33, 38, 391, 4, 6, 12
352, 5, 7, 33, 35, 381, 3, 6, 8, 11, 12
365, 36, 391, 6, 12
375, 36, 373, 4, 12
402, 35, 38, 401, 3, 6, 12

Table 3.

Write cT=40000(v1,…,v21)T\mathbf{c}^{\mathsf{T}}=40000(v_1,\ldots,v_{21})^{\mathsf{T}} and define

Ne=[σe,ℓ1mℓ1T ⋯ σe,ℓ21mℓ21T],Δe=det⁡Ne,N_e=[\sigma_{e,\ell_1}m_{\ell_1}^{\mathsf{T}}\ \cdots\ \sigma_{e,\ell_{21}}m_{\ell_{21}}^{\mathsf{T}}],\qquad\Delta_e=\det N_e,
de=cT−∑i=140σe,imiT.d_e=\mathbf{c}^{\mathsf{T}}-\sum_{i=1}^{40}\sigma_{e,i}m_i^{\mathsf{T}}.

Let Ne[r←de]N_e[r \leftarrow d_e] mean replace column rr of NeN_e by ded_e, and put

λe,i={1+det⁡(Ne[r←de])/Δe,i=ℓr (1≤r≤21),1,i∉Be.\lambda_{e,i} = \begin{cases} 1+\det(N_e[r \leftarrow d_e])/\Delta_e, & i=\ell_r\ (1\le r\le21),\\ 1, & i\notin B_e. \end{cases}

Evaluating these integer determinants exactly gives

Δe≠0(0≤e≤40),\Delta_e\ne0 \qquad(0\le e\le40),
det⁡(Ne[r←de])Δe>8(0≤e≤40, 1≤r≤21).\frac{\det(N_e[r \leftarrow d_e])}{\Delta_e}>8 \qquad(0\le e\le40,\ 1\le r\le21).

Thus all weights are at least 1 (basis weights exceed 9), and Cramer’s rule gives c=∑i=140λe,iσe,imic=\sum_{i=1}^{40}\lambda_{e,i}\sigma_{e,i}m_i for every ee. Also Δ0≠0\Delta_0\ne0 gives rank⁡M0=21\operatorname{rank} M_0=21. If z≠0z\ne0 has all signed slacks σe,imiz≥0\sigma_{e,i}m_i z\ge0, full column rank makes at least one slack positive, so c(z)>0c(z)>0. 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 m1=u1+100u2+21u5−7u6+u17+u18m_1=u_1+100u_2+21u_5-7u_6+u_{17}+u_{18}. 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 Q={x∈Rd:Lx≥ζ}Q=\{x\in\mathbb{R}^d:Lx\ge\zeta\} be full-dimensional. Suppose a nonempty finite set V⊂Q\mathcal{V}\subset Q is given, each v∈Vv\in\mathcal{V} having exactly dd tight rows, whose matrix LvL_v is invertible. For each of these rows jj, suppose a point vj∈Vv_j\in\mathcal{V} satisfies

Lv(vj−v)=gjej,gj>0.L_v(v_j-v)=g_j e_j,\qquad g_j>0.

where eje_j is the jjth coordinate vector. Then V\mathcal{V} is the complete vertex set, QQ is simple, and its neighbors at vv are precisely the points vjv_j.

Proof. For a linear objective ff, choose v∈Vv\in\mathcal{V} maximizing ff on this finite set. For every x∈Qx\in Q, the vector κ=Lv(x−v)\kappa=L_v(x-v) has nonnegative coordinates and

x−v=∑j=1dκjgj(vj−v).x-v=\sum_{j=1}^{d}\frac{\kappa_j}{g_j}(v_j-v).

Since f(vj−v)≤0f(v_j-v)\le0, this proves f(x)≤f(v)f(x)\le f(v): the list contains a global maximizer for every linear objective.

Let xx be any vertex and choose dd independent tight rows II there. The objective f(y)=−∑i∈ILiyf(y)=-\sum_{i\in I}L_i y is maximized precisely where all these rows are tight, because their slacks are nonnegative. Its unique feasible maximizer is xx. A listed maximizer must therefore equal xx. Conversely each listed point is a vertex by its nonsingular tight system, so the list is complete and every vertex has exactly dd tight rows. Each such row defines a distinct facet locally. Releasing one row while retaining the other d−1d-1 defines an edge. The distinct vertices v,vjv,v_j lie on that one-dimensional face and hence are its two endpoints. Every edge at a simple vertex arises this way. □\square

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 M0M_0, 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

Vert⁡(P)={wv:v∈V},∣I(wv)∣=20,rank⁡(M0)I(wv)=20,\operatorname{Vert}(P) = \{w_v : v \in\mathcal{V}\}, \qquad|I(w_v)| = 20, \qquad\operatorname{rank}(M_0)_{I(w_v)} = 20,

where V\mathcal{V} is the supplied list, wvw_v its ray normalized by c(wv)=1c(w_v)=1, and I(wv)I(w_v) its tight-row set. In particular, PP 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 dP(u,v)≥21d_P(u,v) \ge21, 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 dP(u,v)=21d_P(u,v)=21; 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 n−r+2n-r+2 [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 XX to YY has Z+⊆X+∪Y+Z^+ \subseteq X^+ \cup Y^+ and Z−⊆X−∪Y−Z^- \subseteq X^- \cup Y^- at every vertex ZZ, where Z+={i:Zi=1}Z^+ = \{i : Z_i=1\} and Z−={i:Zi=−1}Z^- = \{i : Z_i=-1\}. 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [12]P. Graham, Supplementary material for a counterexample to the cocircuit diameter conjecture, version 1 (2026). Supplementary data and Lean formalization.DOI
  13. [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.

Paper details

vlnc:W_wda9u488
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI models

View statement
Looking for related papers…
Contents