Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.15394 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909554895224832 |
|---|---|
| author | Kriepke, Björn Schymura, Matthias |
| author_facet | Kriepke, Björn Schymura, Matthias |
| contents | 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 $Δ$ 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 $Δ$, 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 $Δ$-submodular matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15394 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On generic $Δ$-modular integer matrices with two rows Kriepke, Björn Schymura, Matthias Combinatorics 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 $Δ$ 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 $Δ$, 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 $Δ$-submodular matrix. |
| title | On generic $Δ$-modular integer matrices with two rows |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.15394 |