On Generic \(\Delta\)-Modular Integer Matrices with Two Rows
Abstract. The column number question asks for the maximum number of columns of an integer matrix with the property that all its rank size minors are bounded by a fixed parameter [Formula: see text] in absolute value. Polynomial upper bounds have been proved in various settings in recent years, with consequences for algorithmic questions in integer linear programming and matroid theory. In this paper, we focus on the exact determination of the maximum column number of such matrices with two rows and no vanishing 2-minors. We prove that for large enough [Formula: see text], this number is a quasi-linear function, nondecreasing, and always even. Such basic structural properties of column number functions are barely known, but may be expected to hold in other settings as well. Moreover, our results identify the unique excluded (co)rank two minors for the class of matroids that are representable as a [Formula: see text]-submodular matrix.