A counterexample to the cocircuit diameter conjecture

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Peter Graham ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

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.

Author comments: Zenodo archive: https://doi.org/10.5281/zenodo.23765669. Lean 4 development, in its folder lean: https://github.com/6/clank-lab/tree/cocircuit-diameter-counterexample-v1/results/cocircuit-diameter-counterexample . What Lean checks (Lean 4.19.0 with a pinned Mathlib; axioms propext, Classical.choice and Quot.sound only): the theorem ADKZPricing.Generated.source_frozen_endpoint, that some rational 80x41 matrix with every 41-row minor nonzero has two real signed cocircuits, with complementary 40-element zero sets and positive entries elsewhere, that no walk of at most 41 edges joins in the full cocircuit graph (all signed cocircuits as vertices). Seven Lean theorems show that its cocircuit, adjacency and walk definitions agree with those of Section 1. Lean also checks the source matrix M_0's vertex and edge certificate and the bound d_P(u,v) >= 21. What Lean leaves outside: (1) the passage from the sign covectors of a real matrix to the realizable oriented matroid of Theorem 1, the standard interpretation; (2) the matrix of Section 3: Lean's matrix is given only existentially, from its own positive functional and perturbations, and is not identified with the printed one, whose Vandermonde perturbations are proved only in the text; (3) the printed positive functional of Appendix A, proved in the text and checked by an exact Python checker; (4) the upper bounds d_P(u,v) = 21 (exact Python checkers) and 42 (Remark 8, written). The full Lean build needs about 88 GiB of memory and half a day. License: the paper text is deposited here under CC BY 4.0; the Lean development and the checkers stay under Apache-2.0 in the published repository.

Provenance statement

The proofs, the Lean formalization, the certificate checkers and the text were produced by AI models, working under the author's direction. Human understanding (author): I follow the statements, not every proof step.

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 (https://doi.org/10.1006/eujc.2001.0481). Statement locators refer to the May 4, 2001 author version (https://finschi.com/math/publ/2001-05-04_Babson-Finschi-Fukuda_Cocircuit-Graphs-Orientation-Reconstruction.pdf).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 (https://doi.org/10.3929/ethz-a-004255224). Author copy (https://finschi.com/math/publ/2001-08-31_Finschi_A-Graph-Theoretical-Approach-for-Reconstruction-and-Generation-of-Oriented-Matroids.pdf).DOI
  3. S. Felsner, R. Gómez, K. Knauer, J. J. Montellano-Ballesteros and R. Strausz, 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 (https://doi.org/10.1016/j.ejc.2010.07.012). arXiv:1001.3534v1 (https://arxiv.org/abs/1001.3534v1) (2010; statement numbering).arXivDOI
  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 (https://doi.org/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 (https://www.combinatorics.org/files/Surveys/ds4/ds4v4-2024.pdf).link
  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 (https://doi.org/10.1112/plms/pdu064). arXiv:1202.4701v2 (https://arxiv.org/abs/1202.4701v2) (statement numbering).arXivDOI
  7. F. Santos, A counterexample to the Hirsch conjecture , Annals of Mathematics 176 (2012), 383--412. doi:10.4007/annals.2012.176.1.7 (https://doi.org/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 (https://doi.org/10.1145/3573105.3575678). arXiv:2301.04060v1 (https://arxiv.org/abs/2301.04060v1) (statement and page numbering).arXivDOI
  9. K. Bérczi, K. Knauer, L. P. Montejano and B. Nádor, Embracing exchange sequences and oriented matroid polyhedron diameter , arXiv:2606.19573v2 (https://arxiv.org/abs/2606.19573v2) (2026).arXiv
  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 (https://arxiv.org/abs/2502.05199v1) (2025).arXiv
Show all 13 referencesShow fewer references
  1. X. Allamigeon, Y. Id-Sahra and P.-Y. Strub, Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration , arXiv:2610.11913v1 (https://arxiv.org/abs/2610.11913v1) (2026).arXiv
  2. P. Graham, Supplementary material for A counterexample to the cocircuit diameter conjecture , version 1 (2026). Supplementary data and Lean formalization (https://github.com/6/clank-lab/tree/cocircuit-diameter-counterexample-v1/results/cocircuit-diameter-counterexample).link
  3. 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 (https://ems.press/content/serial-article-files/46818).link

Version history

  1. v1 · 11 pagesSubmitted by P. GrahamZenodo archive: https://doi.org/10.5281/zenodo.23765669. Lean 4 development, in its folder lean: https://github.com/6/clank-lab/tree/cocircuit-diameter-counterexample-v1/results/cocircuit-diameter-counterexample . What Lean checks (Lean 4.19.0 with a pinned Mathlib; axioms propext, Classical.choice and Quot.sound only): the theorem ADKZPricing.Generated.source_frozen_endpoint, that some rational 80x41 matrix with every 41-row minor nonzero has two real signed cocircuits, with complementary 40-element zero sets and positive entries elsewhere, that no walk of at most 41 edges joins in the full cocircuit graph (all signed cocircuits as vertices). Seven Lean theorems show that its cocircuit, adjacency and walk definitions agree with those of Section 1. Lean also checks the source matrix M_0's vertex and edge certificate and the bound d_P(u,v) >= 21. What Lean leaves outside: (1) the passage from the sign covectors of a real matrix to the realizable oriented matroid of Theorem 1, the standard interpretation; (2) the matrix of Section 3: Lean's matrix is given only existentially, from its own positive functional and perturbations, and is not identified with the printed one, whose Vandermonde perturbations are proved only in the text; (3) the printed positive functional of Appendix A, proved in the text and checked by an exact Python checker; (4) the upper bounds d_P(u,v) = 21 (exact Python checkers) and 42 (Remark 8, written). The full Lean build needs about 88 GiB of memory and half a day. License: the paper text is deposited here under CC BY 4.0; the Lean development and the checkers stay under Apache-2.0 in the published repository.CurrentNov 20, 2026