Existence of a $d$-dimensional spindle with circuit length at least $d+1$ (Black–Borgwardt–Brugger, Open Question 1.1)

Spindles (Dantzig figures) are the only mechanism known to produce counterexamples to the Hirsch conjecture on the graph diameter of polytopes: Santos' 5-dimensional spindle of combinatorial length 6, wedged upward, refuted the conjecture in dimension 43. Whether this mechanism can also break the circuit diameter conjecture — the circuit analogue of the Hirsch bound and the main open problem of circuit diameter theory — hinges on one structural question posed as Open Question 1.1 by Black, Borgwardt and Brugger: does there exist a $d$-dimensional spindle whose circuit length — the maximum, over the two apex-to-apex directions, of the length of a shortest circuit walk between its apices (circuit walks need not be reversible, so the two directions are distinguished) — is at least $d+1$? The source paper proved that all three known 5-dimensional spindles, and the explicit high-dimensional Hirsch counterexamples built from them, satisfy the conjectured circuit bound, but the general existence question — open even for simple spindles, and a negative answer believed to imply the full circuit diameter conjecture — remains unresolved.

Background

The graph (combinatorial) diameter of a polytope is the smallest number of edges needed to travel between any two of its vertices along the polytope's graph, i.e., the network of vertices and edges (the 1-skeleton). The Hirsch conjecture (1957) asserted that this diameter is at most $f-d$ for every $d$-dimensional polytope with $f$ facets. A spindle, also called a Dantzig figure, is a polytope with two distinguished vertices $u$ and $v$, called apices, such that every facet of the polytope contains exactly one of $u$ and $v$; its length is the graph distance between the apices. The Hirsch conjecture was shown in the 1960s to be equivalent to restricted forms, including the d-step conjecture, the special case asking whether every $d$-dimensional spindle with $2d$ facets has length at most $d$ (Borgwardt, Stephen and Yusun recount these reductions). Santos disproved the Hirsch conjecture in 2012 by constructing a highly degenerate 5-dimensional spindle $S_5^{48}$ with 48 facets and length 6 between its apices; a standard lifting operation called wedging, which turns a $d$-dimensional spindle of length exceeding $d$ into a $(d+1)$-dimensional spindle with one more facet whose length exceeds $d+1$, then produced a 43-dimensional polytope with 86 facets whose diameter exceeds the Hirsch bound. Matschke, Santos and Weibel later found smaller 5-dimensional spindles $S_5^{28}$ and $S_5^{25}$ (also of length 6), yielding Hirsch counterexamples in dimensions 23 and 20. These were, as of the source paper, the only known bounded counterexamples.

Circuits generalize edge directions. For a polyhedron given by finitely many linear inequalities, its circuits are the elementary vectors of the constraint system — the nonzero solutions of the homogeneous system with inclusion-minimal support — equivalently the edge directions of the polytope and of all its images under linear maps. A circuit walk from a point $x^0$ to a point $x^k$ moves in each step along a circuit direction of the polyhedron as far as possible (a maximal step), possibly through the relative interiors of faces rather than only along edges. The circuit diameter, introduced by Borgwardt, Finhold and Hemmecke, replaces shortest edge walks by shortest circuit walks between vertex pairs; since every edge walk is a circuit walk (each edge step is a maximal step along a circuit), the circuit diameter never exceeds the graph diameter. The circuit diameter conjecture (CDC) asserts that the circuit diameter of a $d$-dimensional polyhedron with $f$ facets is at most $f-d$. It is the analogue of the Hirsch bound but a logically weaker statement — it upper-bounds a quantity that is at most the graph diameter — which is why it survived Santos' counterexample. It matters algorithmically because it bounds the worst-case iteration count of circuit augmentation schemes, a family of combinatorial algorithms for linear programming that generalize the simplex method. Only the polynomial version of the CDC — a bound polynomial in the facet and dimension counts — was recently settled, by Natura (2026); the linear bound $f-d$ remains open and is described as the main open problem of the area.

Because the Hirsch conjecture fell to a spindle, the natural test of the CDC is whether spindles can also violate the circuit bound. Stephen and Yusun showed that the Klee–Walkup counterexample to the unbounded Hirsch conjecture does not transfer: its circuit diameter meets the bound. Black, Borgwardt and Brugger then proved that the circuit length — the maximum, over the two apex-to-apex directions, of the length of a shortest circuit walk between the apices (circuit walks need not be reversible, so the two directions are distinguished) — of all three known 5-dimensional spindles $S_5^{48}$, $S_5^{28}$ and $S_5^{25}$ is at most 5, robustly under mild perturbations, by exploiting the geometry of certain 2-dimensional faces (sufficient conditions under which short circuit walks provably exist); they also computationally verified that the two explicit high-dimensional Hirsch counterexamples of Matschke–Santos–Weibel have circuit length at most their dimension. They supplemented this with structural positive results: if the feasible cone at one apex is contained in the feasible cone at the other, the apices admit a sign-compatible circuit walk of length at most $d$, so such spindles can never violate the bound. The authors posed the question below as their Open Question 1.1, observing that the circuit diameter conjecture for spindles remains interesting beyond the three instances they analyze. They note that a negative answer, and likewise the variant for simple spindles (spindles that are simple polytopes, in which every vertex lies on exactly $d$ facets) posed as Conjecture 3.8 of Borgwardt–Stephen–Yusun, is believed — but not known — to imply the CDC itself. One further subtlety: unlike the combinatorial diameter, the circuit diameter depends on the geometric realization of the polytope, not only on its combinatorial type; the known bounds are proven for the specific realizations in the literature and for perturbations retaining certain 2-face properties, and whether all realizations obey them is itself open.

Problem Statement

Does there exist an integer $d$ and a $d$-dimensional spindle — a polytope with two vertices $u$ and $v$ (the apices) such that every facet contains exactly one of them — whose circuit length is at least $d+1$? Here the circuit length of a spindle is the maximum, over the two apex-to-apex directions, of the minimum number of steps of a circuit walk from one apex to the other, where each step moves along a circuit of the polytope (an elementary vector of its constraint system) with maximal step length, and intermediate points of the walk may lie in the relative interiors of faces; circuit walks need not be reversible, so the direction from $u$ to $v$ and the direction from $v$ to $u$ are distinguished, and the maximum over the two directions is at least $d+1$ exactly when one of them is — so it suffices to exhibit one direction of apex-to-apex circuit distance at least $d+1$. Equivalently: is the circuit distance between the apices of every $d$-dimensional spindle at most $d$ in both directions, for every $d$ and every geometric realization, degenerate or not? The question is open even when restricted to simple spindles (spindles that are simple polytopes, in which every vertex lies on exactly $d$ facets), the variant posed as Conjecture 3.8 of Borgwardt, Stephen and Yusun. The related but separate questions — whether a negative answer implies the circuit diameter conjecture, and whether the known circuit-length bounds for $S_5^{48}$, $S_5^{28}$ and $S_5^{25}$ hold for all their realizations — remain open alongside this one and are not part of this question.

References

1. Alexander E. Black, Steffen Borgwardt, Matthias Brugger, 'On the circuit diameter conjecture for counterexamples to the Hirsch conjecture', Discrete Optimization 58:100910 (2025). DOI 10.1016/j.disopt.2025.100910; arXiv:2302.03977, https://arxiv.org/abs/2302.03977 (source paper)
2. Francisco Santos, 'A counterexample to the Hirsch Conjecture', Annals of Mathematics 176(1):383-412 (2012). DOI 10.4007/annals.2012.176.1.7, https://doi.org/10.4007/annals.2012.176.1.7
3. Benjamin Matschke, Francisco Santos, Christophe Weibel, 'The width of five-dimensional prismatoids', Proceedings of the London Mathematical Society 110(3):647-672 (2015). DOI 10.1112/plms/pdu064, https://doi.org/10.1112/plms/pdu064
4. Steffen Borgwardt, Tamon Stephen, Timothy Yusun, 'On the Circuit Diameter Conjecture', Discrete & Computational Geometry 60(3):558-587 (2018). DOI 10.1007/s00454-018-9995-y; arXiv:1611.08039, https://arxiv.org/abs/1611.08039
5. Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke, 'On the Circuit Diameter of Dual Transportation Polyhedra', SIAM Journal on Discrete Mathematics 29(1):113-121 (2015). DOI 10.1137/140976868, https://doi.org/10.1137/140976868
6. Tamon Stephen, Timothy Yusun, 'The Circuit Diameter of the Klee-Walkup Polyhedron', Electronic Notes in Discrete Mathematics 49:505-512 (2015). DOI 10.1016/j.endm.2015.06.070, https://doi.org/10.1016/j.endm.2015.06.070
7. Bento Natura, 'Circuit Diameter of Polyhedra is Strongly Polynomial', arXiv:2602.06958 (2026). https://arxiv.org/abs/2602.06958
8. Daniel Dadush, Stefan Kober, Zhuan Khye Koh, 'On Circuit Diameter and Straight Line Complexity', arXiv:2602.05699 (2026). https://arxiv.org/abs/2602.05699
9. Alexander E. Black, Christian Nöbel, Raphael Steiner, 'Short circuit walks in fixed dimension', Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 563-573. DOI 10.1137/1.9781611978971.23; arXiv:2510.01916, https://arxiv.org/abs/2510.01916
10. Alexander E. Black, Lei Xue, 'Any Proof of Polynomial Hirsch Must be Completely Incoherent', arXiv:2607.11628 (2026). https://arxiv.org/abs/2607.11628
11. Lasse Wulf, 'Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)', Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) 2025, pp. 531-551. DOI 10.1109/FOCS63196.2025.00029; arXiv:2502.16398, https://arxiv.org/abs/2502.16398
12. Steffen Borgwardt, Weston Grewe, Sean Kafer, Jon Lee, Laura Sanità, 'On the hardness of short and sign-compatible circuit walks', Discrete Applied Mathematics 367:129-149 (2025). DOI 10.1016/j.dam.2025.02.009; arXiv:2402.01066, https://arxiv.org/abs/2402.01066
13. Alexander E. Black, Raphael Steiner, 'Finding Short Paths on Simple Polytopes', arXiv:2603.05482 (2026). https://arxiv.org/abs/2603.05482