{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T17:58:08Z","timestamp":1771955888409,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Brandenburgische TU Cottbus-Senftenberg"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the maximal number of pairwise distinct columns in a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-modular integer matrix with\u00a0<jats:italic>m<\/jats:italic> rows. Recent results by Lee et al.\u00a0provide an asymptotically tight upper bound of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}\\left( m^2\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:msup>\n                        <mml:mi>m<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for fixed\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We complement this and obtain an upper bound of the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\varDelta )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for fixed\u00a0<jats:italic>m<\/jats:italic>, and with the implied constant depending polynomially on\u00a0<jats:italic>m<\/jats:italic>.\n<\/jats:p>","DOI":"10.1007\/s10107-023-01964-2","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T11:56:36Z","timestamp":1684151796000},"page":"61-89","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the maximal number of columns of a $$\\Delta $$-modular integer matrix: bounds and computations"],"prefix":"10.1007","volume":"206","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5156-7953","authenticated-orcid":false,"given":"Matthias","family":"Schymura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,13]]},"reference":[{"issue":"1","key":"1964_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0195-6698(13)80051-0","volume":"11","author":"RP Anstee","year":"1990","unstructured":"Anstee, R.P.: Forbidden configurations, discrepancy and determinants. Eur. J. Comb. 11(1), 15\u201319 (1990)","journal-title":"Eur. J. Comb."},{"key":"1964_CR2","doi-asserted-by":"crossref","unstructured":"Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodular integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1206\u20131219 (2017)","DOI":"10.1145\/3055399.3055473"},{"issue":"1","key":"1964_CR3","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00454-020-00246-4","volume":"66","author":"G Averkov","year":"2021","unstructured":"Averkov, G., Borger, C., Soprunov, I.: Classification of triples of lattice polytopes with a given mixed volume. Discret. Comput. Geom. 66(1), 165\u2013202 (2021)","journal-title":"Discret. Comput. Geom."},{"key":"1964_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-031-06901-7_3","volume-title":"Integer programming and combinatorial optimization","author":"G Averkov","year":"2022","unstructured":"Averkov, G., Schymura, M.: On the Maximal Number of Columns of a $$\\varDelta $$-modular Matrix. In: Aardal, K., Sanit\u00e0, L. (eds.) Integer programming and combinatorial optimization, pp. 29\u201342. Springer International Publishing, Cham (2022)"},{"key":"1964_CR5","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0195-6698(87)80025-2","volume":"8","author":"RE Bixby","year":"1987","unstructured":"Bixby, R.E., Cunningham, W.H.: Short cocircuits in binary matroids. Eur. J. Comb. 8, 213\u2013225 (1987)","journal-title":"Eur. J. Comb."},{"key":"1964_CR6","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Joret, G., Weltge, S., Yuditsky, Y.: Integer programs with bounded subdeterminants and two nonzeros per row. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 13\u201324 (2022)","DOI":"10.1109\/FOCS52979.2021.00011"},{"key":"1964_CR7","unstructured":"Geelen, J., Nelson, P., Walsh, Z.: Excluding a Line from $${\\mathbb{C}}$$-representable Matroids (2021). arxiv:2101.12000"},{"issue":"3","key":"1964_CR8","doi-asserted-by":"publisher","first-page":"1706","DOI":"10.1137\/17M1125728","volume":"32","author":"C Glanzer","year":"2018","unstructured":"Glanzer, C., Weismantel, R., Zenklusen, R.: On the number of distinct rows of a matrix with bounded subdeterminants. SIAM J. Discret. Math. 32(3), 1706\u20131720 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"1964_CR9","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.2140\/pjm.1957.7.1351","volume":"7","author":"I Heller","year":"1957","unstructured":"Heller, I.: On linear systems with integral valued solutions. Pac. J. Math. 7, 1351\u20131364 (1957)","journal-title":"Pac. J. Math."},{"key":"1964_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0024-3795(89)90450-3","volume":"114\u2013115","author":"J Lee","year":"1989","unstructured":"Lee, J.: Subspaces with well-scaled frames. Linear Algebra Appl. 114\u2013115, 21\u201356 (1989)","journal-title":"Linear Algebra Appl."},{"key":"1964_CR11","doi-asserted-by":"crossref","unstructured":"Lee, J., Paat, J., Stallknecht, I., Xu, L.: Polynomial upper bounds on the number of differing columns of $$\\varDelta $$-modular integer programs. Math. Oper. Res. (2023). Ahead of print","DOI":"10.1287\/moor.2022.1339"},{"key":"1964_CR12","doi-asserted-by":"crossref","unstructured":"N\u00e4gele, M., Santiago, R., Zenklusen, R.: Congruency-constrained TU problems beyond the bimodular case. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2743\u20132790 (2022)","DOI":"10.1137\/1.9781611977073.108"},{"key":"1964_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Combin. Theory Ser. A 13, 145\u2013147 (1972)","journal-title":"J. Combin. Theory Ser. A"},{"key":"1964_CR14","series-title":"Wiley-Interscience Series in Discrete Mathematics","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Ltd, Chichester (1986)"},{"key":"1964_CR15","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41, 247\u2013261 (1972)","journal-title":"Pac. J. Math."},{"key":"1964_CR16","unstructured":"The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.1) (2020). https:\/\/www.sagemath.org"},{"key":"1964_CR17","first-page":"161","volume":"88","author":"WT Tutte","year":"1958","unstructured":"Tutte, W.T.: A homotopy theorem for matroids. II. Trans. Am. Math. Soc. 88, 161\u2013174 (1958)","journal-title":"II. Trans. Am. Math. Soc."},{"key":"1964_CR18","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01964-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01964-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01964-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:20:31Z","timestamp":1721823631000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01964-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,13]]},"references-count":18,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1964"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01964-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,13]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}