Doignon's theorem in

geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

is an analogue of

Helly's theorem Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's ...

for the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...

. It states that, if a family of

convex set In geometry, a set of points is convex if it contains every line segment between two points in the set. For example, a solid cube (geometry), cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is n ...

s in

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

have the property that the intersection of every

2^d

contains an integer point, then the intersection of all of the sets contains an integer point. Therefore,

integer linear program An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...

s form an LP-type problem of combinatorial and can be solved by certain generalizations of

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

algorithms in an amount of time that is linear in the number of constraints of the problem and

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

in its The same theorem applies more generally to any lattice, not just the integer The theorem can be classified as belonging to

convex geometry In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of num ...

discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geom ...

, and the

geometry of numbers Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice (group), lattice in \mathbb R^n, and the study of these lattices provides fundam ...

. It is named after Belgian mathematician and mathematical psychologist Jean-Paul Doignon, who published it in 1973. Doignon credits

Francis Buekenhout Francis Buekenhout (born 23 April 1937 in Ixelles near Brussels) is a Belgian mathematician who introduced Buekenhout geometries and the concept of quadratic sets. Career Buekenhout studied at the University of Brussels under Jacques Tits and ...

with posing the question answered by this It is also called the Doignon–Bell–Scarf theorem, crediting

mathematical economists Mathematical economics is the application of mathematical methods to represent theories and analyze problems in economics. Often, these applied methods are beyond simple geometry, and may include differential and integral calculus, difference ...

David E. Bell and

Herbert Scarf Herbert Eli "Herb" Scarf (July 25, 1930 – November 15, 2015) was an American mathematical economist and Sterling Professor of Economics at Yale University. Education and career Scarf was born in Philadelphia, the son of Jewish emigrants from ...

, who both rediscovered it and pointed out its applications to integer The result is tight: there exist systems of half-spaces for which every

2^d-1

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 A unit cube, more formally a cube of side 1, is a cube whose sides are 1 unit long.. See in particulap. 671. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.. Unit hypercube The term '' ...

. Another way of phrasing the result is that the Helly number of convex subsets of the integers is 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 A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

that contains no other point from the Generalizing both Helly's theorem and Doignon's theorem, the Helly number of the

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...

\mathbb^d\times\mathbb^k

References

{{reflist, refs= {{citation , 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 {{citation , 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 {{citation , 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 {{citation , last = Bell , first = David E. , doi = 10.1002/sapm1977562187 , issue = 2 , journal =

Studies in Applied Mathematics The journal ''Studies in Applied Mathematics'' is published by Wiley–Blackwell on behalf of the Massachusetts Institute of Technology. It features scholarly articles on mathematical applications in allied fields, notably computer science, ...

, mr = 462617 , pages = 187–188 , title = A theorem concerning the integer lattice , volume = 56 , year = 1977 {{citation , 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 '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was es ...

, mr = 3757097 , pages = 352–371 , title = Sublinear bounds for a quantitative Doignon–Bell–Scarf theorem , volume = 32 , year = 2018, arxiv = 1512.07126 {{citation , 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 {{citation , 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 ''Proceedings of the National Academy of Sciences of the United States of America'' (often abbreviated ''PNAS'' or ''PNAS USA'') is a peer-reviewed multidisciplinary scientific journal. It is the official journal of the National Academy of Scie ...

, 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 Theorems in convex geometry Theorems in discrete geometry Geometry of numbers Lattice points