关于具有两行的通用 $Δ$-模整数矩阵

On generic $Δ$-modular integer matrices with two rows

摘要 Abstract

列数问题旨在确定一个整数矩阵的最大列数,该矩阵的所有秩大小的子式在绝对值上都被固定参数 $Δ$ 所限制。近年来在不同背景下证明了多项式的上界,这对整数线性规划和拟阵论中的算法问题产生了影响。本文聚焦于两行且无零 $2$-子式的此类矩阵最大列数的确切确定。我们证明,当 $Δ$ 足够大时,该数量是一个拟线性函数,非递减且始终为偶数。这类列数函数的基本结构性质鲜为人知,但预计在其他背景下也成立。此外,我们的结果识别出了一类可表示为 $Δ$-次模矩阵的拟阵所对应的唯一排除(共)秩二子式。

The column number question asks for the maximal number of columns of an integer matrix with the property that all its rank size minors are bounded by a fixed parameter $\Delta$ 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 maximal column number of such matrices with two rows and no vanishing $2$-minors. We prove that for large enough $\Delta$, this number is a quasi-linear function, non-decreasing and always even. Such basic structural properties of column number functions are barely known, but 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 $\Delta$-submodular matrix.