Doignon's theorem
Doignon's theorem in geometry is an analogue of Helly's theorem for the integer lattice. It states that, if a family of convex sets in {{nowrap|-dimensional}} Euclidean space have the property that the intersection of every contains an integer point, then the intersection of all of the sets contains an integer point. Therefore, {{nowrap|-dimensional}} integer linear programs form an LP-type problem of combinatorial {{nowrap|dimension ,}} and can be solved by certain generalizations of linear programming algorithms in an amount of time that is linear in the number of constraints of the problem and fixed-parameter tractable in its {{nowrap|dimension.{{r|ads}}}} The same theorem applies more generally to any lattice, not just the integer {{nowrap|lattice.{{r|doignon}}}}
The theorem can be classified as belonging to convex geometry, discrete geometry, and the geometry of numbers. It is named after Belgian mathematician and mathematical psychologist Jean-Paul Doignon, who published it in 1973. Doignon credits Francis Buekenhout with posing the question answered by this {{nowrap|theorem.{{r|doignon}}}} It is also called the Doignon–Bell–Scarf theorem,{{r|chz}} crediting mathematical economists David E. Bell and Herbert Scarf, who both rediscovered it {{nowrap|in 1977{{r|bell|scarf}}}} and pointed out its applications to integer {{nowrap|programming.{{r|ads}}}}
The result is tight: there exist systems of half-spaces for which every have an integer point in their intersection, but for which the whole system has no integer intersection. Such a system can be obtained, for instance, by choosing halfspaces that contain all but one vertex of the unit cube. Another way of phrasing the result is that the Helly number of convex subsets of the integers is {{nowrap|exactly .}} More generally, the Helly number of any discrete set of Euclidean points equals the maximum number of points that can be chosen to form the vertices of a convex polytope that contains no other point from the {{nowrap|set.{{r|abfjn}}}} Generalizing both Helly's theorem and Doignon's theorem, the Helly number of the Cartesian product {{nowrap|is .{{r|aw}}}}
References
{{reflist|refs=
| last1 = Ambrus | first1 = Gergely
| last2 = Balko | first2 = Martin
| last3 = Frankl | first3 = Nóra
| last4 = Jung | first4 = Attila
| last5 = Naszódi | first5 = Márton
| editor1-last = Chambers | editor1-first = Erin W. | editor1-link = Erin Wolf Chambers
| editor2-last = Gudmundsson | editor2-first = Joachim
| contribution = On Helly numbers of exponential lattices
| doi = 10.4230/LIPIcs.SoCG.2023.8
| pages = 8:1–8:16
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 39th International Symposium on Computational Geometry, SoCG 2023, June 12–15, 2023, Dallas, Texas, USA
| volume = 258
| year = 2023| doi-access = free
}}
| last1 = Amenta | first1 = Nina | author1-link = Nina Amenta
| last2 = De Loera | first2 = Jesús A. | author2-link = Jesús A. De Loera
| last3 = Soberón | first3 = Pablo
| editor1-last = Harrington | editor1-first = Heather A. | editor1-link = Heather Harrington
| editor2-last = Omar | editor2-first = Mohamed
| editor3-last = Wright | editor3-first = Matthew
| arxiv = 1508.07606
| contribution = Helly's theorem: new variations and applications
| doi = 10.1090/conm/685
| location = Providence, Rhode Island
| mr = 3625571
| pages = 55–95
| publisher = American Mathematical Society
| series = Contemporary Mathematics
| title = Proceedings of the AMS Special Session on Algebraic and Geometric Methods in Applied Discrete Mathematics held in San Antonio, TX, January 11, 2015
| volume = 685
| year = 2017| isbn = 978-1-4704-2321-6 }}
| last1 = Averkov | first1 = G.
| last2 = Weismantel | first2 = R.
| doi = 10.1515/advgeom.2011.028
| issue = 1
| journal = Advances in Geometry
| mr = 2911157
| pages = 19–28
| title = Transversal numbers over subsets of linear spaces
| volume = 12
| year = 2012| arxiv = 1002.0948
}}
| last = Bell | first = David E.
| doi = 10.1002/sapm1977562187
| issue = 2
| journal = Studies in Applied Mathematics
| mr = 462617
| pages = 187–188
| title = A theorem concerning the integer lattice
| volume = 56
| year = 1977}}
| last1 = Chestnut | first1 = Stephen R.
| last2 = Hildebrand | first2 = Robert
| last3 = Zenklusen | first3 = Rico
| doi = 10.1137/16M1100095
| issue = 1
| journal = SIAM Journal on Discrete Mathematics
| mr = 3757097
| pages = 352–371
| title = Sublinear bounds for a quantitative Doignon–Bell–Scarf theorem
| volume = 32
| year = 2018| arxiv = 1512.07126
}}
| last = Doignon | first = Jean-Paul
| doi = 10.1007/BF01949705
| journal = Journal of Geometry
| mr = 387090
| pages = 71–85
| title = Convexity in {{not a typo|cristallographical}} lattices
| volume = 3
| year = 1973}}
| last = Scarf | first = Herbert E. | author-link = Herbert Scarf
| doi = 10.1073/pnas.74.9.3637
| issue = 9
| journal = Proceedings of the National Academy of Sciences of the United States of America
| mr = 452678
| pages = 3637–3641
| title = An observation on the structure of production sets with indivisibilities
| volume = 74
| year = 1977| doi-access = free | pmid = 16592435 | pmc = 431672
| bibcode = 1977PNAS...74.3637S }}
}}
Category:Theorems in convex geometry