Unimodular Polytopes and Column Number Bounds on Polytopal Totally Unimodular Matrices via Seymour’s Decomposition Theorem
Abstract
Abstract. We prove a sharp upper bound on the number of distinct columns of a totally unimodular matrix with column sums 1 improving upon Heller’s classical bound. The proof uses Seymour’s decomposition theorem. Such matrices are closely related to unimodular polytopes: lattice polytopes where the vertices of every full-dimensional subsimplex form an affine lattice basis. This is an interesting subclass of 0/1-polytopes and contains, for instance, edge polytopes of bipartite graphs. Our main result on totally unimodular matrices implies a sharp upper bound on the number of vertices of unimodular polytopes.
Fields of Study & Subjects
graph theory and CDMA systems
Graph theory and applications
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- SIAM Journal on Discrete Mathematics
- Volume
- 40
- Issue
- 1
- Pages
- 223–236
- Publication date
- 24 February 2026
- Language
- EN