Unimodular polytopes and column number bounds on polytopal totally unimodular matrices via Seymour's decomposition theorem

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.

arXiv comment16 pages; Jon Lee pointed out that our main result follows from Corollary 4.3 in his article "Turán's triangle theorem and binary matroids"

References in corpus (3)

• Centrally symmetric configurations of integer matrices
• $2$-Modular Matrices
• Nef-partitions arising from unimodular configurations