Polynomial Upper Bounds on the Number of Differing Columns of Δ-Modular Integer Programs.

The article focuses on establishing new bounds and combinatorial properties for integer-valued matrices with bounded determinants, particularly Δ-modular matrices, which are central in integer programming (IP). It provides the first polynomial upper bound on the maximum number of differing columns, denoted by 𝔠(Δ, m), in such matrices that depends polynomially on both the determinant bound Δ and the number of equations m. A key result is a tight exact formula for 𝔠(2, m) when Δ = 2 (bimodular matrices), generalizing Heller's classical bound for totally unimodular matrices (Δ = 1). The paper also derives the first polynomial proximity bound between IP solutions and their linear relaxations in terms of Δ and m, and connects these bounds to the height of Graver basis elements. The analysis relies on detailed combinatorial and matroid-theoretic properties of bimodular matrices, including the structure and uniqueness of circuits (minimal dependent sets), and provides constructions demonstrating the tightness of the bounds.