Totally Equimodular Polyhedra: Diameters and Pivots
Abstract
Totally equimodular matrices generalize totally unimodular matrices and arise in the theory of box-total dual integrality. We prove that every nonempty pointed polyhedron admitting a rational totally equimodular description has combinatorial diameter at most 8d 3 (1 + 2 log d), where d is its intrinsic dimension. The bound is independent of the number of inequalities, the right-hand side, and the magnitudes of subdeterminants, it applies to unbounded and degenerate polyhedra, and it matches the best asymptotic bound known for totally unimodular matrices. This resolves a question raised by Lancini and Pisanu. We also give a sharp upper bound 2d 2 on the number of facets of a d-dimensional totally equimodular polytope. Finally, we show that a shadowsimplex algorithm uses O(d 4 log d) expected optimization pivots from a feasible basis on full-dimensional pointed polyhedra, and O(md 4 log d) expected feasibility pivots for descriptions with m inequalities and full column rank.
Related
- Generalized Quasi-Symmetric Nets: A Constructive Approach to the Equimodular Elliptic Type and to Flexible m × n Nets
- Infinite light rays and infinite clusters with infinitely many pivots
- On the Hessian Conjecture in Lorentzian Signature: Constant Pivots and Hesse Systems
- Cayley graph diameters for fixed cycle types are eventually quasipolynomial
- Sublinear Power-Law Growth of Level Set Diameters in Heterogeneous F-KPP Equations
BibTeX
@misc{lancini2026totally,
title = {{Totally Equimodular Polyhedra: Diameters and Pivots}},
author = {Emiliano Lancini},
howpublished = {HAL},
year = {2026},
month = nov,
url = {https://hal.science/hal-05849014v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Totally Equimodular Polyhedra: Diameters and Pivots
AU - Emiliano Lancini
PY - 2026
DA - 2026/11/02
PB - HAL
UR - https://hal.science/hal-05849014v1
AB - Totally equimodular matrices generalize totally unimodular matrices and arise in the theory of box-total dual integrality. We prove that every nonempty pointed polyhedron admitting a rational totally equimodular description has combinatorial diameter at most 8d 3 (1 + 2 log d), where d is its intrinsic dimension. The bound is independent of the number of inequalities, the right-hand side, and the magnitudes of subdeterminants, it applies to unbounded and degenerate polyhedra, and it matches the best asymptotic bound known for totally unimodular matrices. This resolves a question raised by Lancini and Pisanu. We also give a sharp upper bound 2d 2 on the number of facets of a d-dimensional totally equimodular polytope. Finally, we show that a shadowsimplex algorithm uses O(d 4 log d) expected optimization pivots from a feasible basis on full-dimensional pointed polyhedra, and O(md 4 log d) expected feasibility pivots for descriptions with m inequalities and full column rank.
ER -