{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:46:14Z","timestamp":1787319974104,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021 165866"],"award-info":[{"award-number":["200021 165866"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [ Combinatorica, 37 (2017), pp. 313--332] generalizes the famous Doignon--Bell--Scarf theorem on the existence of integer solutions to systems of linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly $k$ integer points in ${R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $\\mathbb{R}^n$ that contains exactly $k$ integer points has a relaxation to at most $c(n,k)$ of its inequalities that will define a new polyhedron with the same integer points. They prove that $c(n,k) = O(k)2^n$. In this paper, we improve the bound asymptotically to be sublinear in $k$, that is, $c(n,k) = o(k) 2^n$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension n=2, our upper and lower bounds match to within a constant factor.<\/jats:p>","DOI":"10.1137\/16m1100095","type":"journal-article","created":{"date-parts":[[2018,2,1]],"date-time":"2018-02-01T12:14:17Z","timestamp":1517487257000},"page":"352-371","source":"Crossref","is-referenced-by-count":4,"title":["Sublinear Bounds for a Quantitative Doignon--Bell--Scarf Theorem"],"prefix":"10.1137","volume":"32","author":[{"given":"Stephen R.","family":"Chestnut","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Hildebrand","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3266-9"},{"key":"atypb2","first-page":"37","author":"Aliev I.","year":"2014","journal-title":"New York"},{"key":"atypb3","unstructured":"N. Amenta, J. A. De Loera, and P. Sobero\u0301n,\n                      Helly's Theorem: New Variations and Applications\n                      , preprint,arXiv:1508.07606, 2015."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0143105-7"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/110850463"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2017.04.003"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1515\/advgeom.2011.028"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0917-y"},{"key":"atypb9","first-page":"162","author":"Balog A.","year":"1991","journal-title":"ACM"},{"key":"atypb10","first-page":"87","author":"Ba\u0301ra\u0301ny I.","year":"2008","journal-title":"RI"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s002080050217"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0012-0"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1977562187"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9376-2"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201036"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2011.03.001"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01563613"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. C. Schwarzkopf,\n                      Computational Geometry\n                      , Springer, New York, 2000.","DOI":"10.1007\/978-3-662-04245-8"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01949705"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0404030"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1112\/S002557931500039X"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01304101"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32803.x"},{"key":"atypb24","first-page":"89","author":"Ivic\u0301 A.","year":"2006","journal-title":"Stuttgart"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90003-5"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0855-0"},{"key":"atypb27","unstructured":"J. A. de Loera, R. N. la Haye, D. Oliveros, and E. Rolda\u0301n-Pensado,\n                      Helly Numbers of Algebraic Subsets of ${R}^d$\n                      , preprint,arXiv:1508.02380, 2015."},{"key":"atypb28","unstructured":"L. Lova\u0301sz,\n                      Geometry of numbers and integer programming\n                      , in Mathematical Programming: Recent Developments and Applications, M. Iri and K. Tanabe, eds., Kluwer, Dordrecht, the Netherlands, 1989, pp. 177-210."},{"key":"atypb29","first-page":"98","volume":"13","author":"Pach J.","year":"2003","journal-title":"Geombinatorics"},{"key":"atypb30","first-page":"85","volume":"2","author":"Rabinowitz S.","year":"1993","journal-title":"Geombinatorics"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02454387"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091506001398"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.74.9.3637"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-013-0049-0"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00441-1"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"T. Tao and V. H. Vu,\n                      Additive Combinatorics\n                      , Cambridge Stud. Adv. Math., Cambridge University Press, New York, 2006.","DOI":"10.1017\/CBO9780511755149"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1100095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:55Z","timestamp":1787316835000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1100095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1100095"],"URL":"https:\/\/doi.org\/10.1137\/16m1100095","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}