{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:39:19Z","timestamp":1787326759571,"version":"3.56.0"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We study two combinatorial parameters, which we denote by $f(S)$ and $h(S)$, associated with an arbitrary set $S \\subseteq \\mathbb{R}^d$, where $d \\in \\mathbb{N}$. In the nondegenerate situation, $f(S)$ is the largest possible number of facets of a $d$-dimensional polyhedron $L$ such that the interior of $L$ is disjoint with $S$ and $L$ is inclusion-maximal with respect to this property. The parameter $h(S)$ is the Helly number of the family of all sets that can be given as the intersection of $S$ with a convex subset of $\\mathbb{R}^d$. We obtain the inequality $f(S) \\le h(S)$ for an arbitrary $S$, and the equality $f(S)=h(S)$ for every discrete $S$. Furthermore, motivated by research in integer and mixed-integer optimization, we show that $2^d$ is the sharp upper bound on $f(S)$ in the case $S = (\\mathbb{Z}^d \\times \\mathbb{R}^n) \\cap C$, where $n \\ge 0$ and $C \\subseteq \\mathbb{R}^{d+n}$ is convex. The presented material generalizes and unifies results of various authors, including the result $h(\\mathbb{Z}^d) = 2^d$ of Doignon, the related result $f(\\mathbb{Z}^d)=2^d$ of Lov\u00e1sz, and the inequality $f(\\mathbb{Z}^d \\cap C) \\le 2^d$, which has recently been proved for every convex set $C \\subseteq \\mathbb{R}^d$ by Mor\u00e1n and Dey.<\/jats:p>","DOI":"10.1137\/110850463","type":"journal-article","created":{"date-parts":[[2013,9,26]],"date-time":"2013-09-26T11:24:39Z","timestamp":1380194679000},"page":"1610-1624","source":"Crossref","is-referenced-by-count":26,"title":["On Maximal $S$-Free Sets and the Helly Number for the Family of $S$-Convex Sets"],"prefix":"10.1137","volume":"27","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,9,26]]},"reference":[{"key":"atypb1","first-page":"1","author":"Andersen K.","year":"2007","journal-title":"Berlin"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s13366-012-0092-8"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s13366-011-0028-8"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0510"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1515\/advgeom.2011.028"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.1.19"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/S0001-8708(02)00037-3"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0461"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/090756375"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1977562187"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"V. Boltyanski, H. Martini, and P. S. Soltan,<i>Excursions into Combinatorial Geometry<\/i> Universitext, Springer-Verlag, Berlin, 1997.","DOI":"10.1007\/978-3-642-59237-9"},{"key":"atypb12","first-page":"105","volume":"16","author":"Conforti M.","year":"2011","journal-title":"Surveys Oper. Res. Management Sci."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0476-9"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/090754388"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01949705"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.09.002"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-01-02763-5"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-005-1169-z"},{"key":"atypb19","unstructured":"P. M. Gruber,<i>Convex and Discrete Geometry<\/i> Grundl. Math. Wiss. 336, Springer, Berlin, 2007."},{"key":"atypb20","unstructured":"P. M. Gruber and C. G. Lekkerkerker,<i>Geometry of Numbers<\/i> 2nd ed., North-Holland Math. Lib. 37, North-Holland, Amsterdam, 1987."},{"key":"atypb21","unstructured":"P. M. Gruber and J. M. Wills, eds.<i>Handbook of Convex Geometry, Vol. A, B<\/i> North-Holland, Amsterdam, 1993."},{"key":"atypb22","first-page":"177","author":"Lov\u00e1sz L.","year":"1989","journal-title":"Tokyo"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/100796947"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0404039"},{"key":"atypb25","unstructured":"R. T. Rockafellar,<i>Convex Analysis<\/i> Princeton Math. Ser. 28, Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.74.9.3637"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"R. Schneider,<i>Convex Bodies: The Brunn-Minkowski Theory<\/i> Encyclopedia Math. Appl. 44, Cambridge University Press, Cambridge, 1993.","DOI":"10.1017\/CBO9780511526282"},{"key":"atypb28","unstructured":"A. Schrijver,<i>Theory of Linear and Integer Programming<\/i> Wiley-Intersci. Ser. Discrete Math., John Wiley & Sons, Chichester, UK, 1986."},{"key":"atypb29","unstructured":"M. J. Todd,<i>The Number of Necessary Constraints in an Integer Program: A New Proof of Scarf's Theorem<\/i> Technical Report 355, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1977."},{"key":"atypb30","unstructured":"M. L. J. van de Vel,<i>Theory of Convex Structures<\/i> North-Holland Math. Lib. 50, North-Holland, Amsterdam, 1993."},{"key":"atypb31","first-page":"2996","author":"Weismantel R.","year":"2010","journal-title":"India"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110850463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:35:46Z","timestamp":1787322946000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110850463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110850463"],"URL":"https:\/\/doi.org\/10.1137\/110850463","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}