ドワニョンの定理

幾何学におけるドワニョンの定理は、整数格子に対するヘリーの定理の類似物である。これは、次元ユークリッド空間の凸集合族が、すべての集合の交点に整数点が含まれるという性質を持つ場合、すべての集合の交点に整数点が含まれることを述べている。したがって、次元整数線形計画法は、組み合わせ次元のLP 型問題を形成し、線形計画アルゴリズムの特定の一般化によって、問題の制約の数に線形で、その次元で固定パラメータが扱いやすい時間で解くことができる。 ^[1]同じ定理は、整数格子 だけでなく、任意の格子に一般的に適用される。^[2]${\displaystyle d}$ ${\displaystyle 2^{d}}$${\displaystyle d}$ ${\displaystyle 2^{d}}$

この定理は、凸幾何学、離散幾何学、および数の幾何学に属するものとして分類できます。この定理は、1973年に発表したベルギーの数学者で数理心理学者のジャン=ポール・ドワニョンにちなんで名付けられました。ドワニョンはこの定理によって答えられる問題を提起したのはフランシス・ビューケンハウトであるとしています。^[2]この定理は、ドワニョン・ベル・スカーフ定理とも呼ばれています。[ ^{3]これは、}数理経済学者のデイビッド・E・ベルとハーバート・スカーフの功績によるもので、2人は1977年にこの定理を再発見し^{[4] [5]}、整数計画法への応用を指摘しました。^[1]

結果は厳密である。つまり、すべての半空間の交点に整数点があるが、システム全体では整数交点がないような半空間のシステムが存在する。このようなシステムは、たとえば、単位立方体の 1 つの頂点を除くすべての頂点を含む半空間を選択することにより得られる。結果を別の方法で表現すると、整数の凸部分集合のヘリー数はちょうど である。より一般的には、ユークリッド点の任意の離散集合のヘリー数は、その集合の他の点を含まない凸多面体の頂点を形成するために選択できる点の最大数に等しい。^[6]ヘリーの定理とドワニョンの定理の両方を一般化すると、直積のヘリー数はである。^[7]${\displaystyle 2^{d}-1}$${\displaystyle 2^{d}}$ ${\displaystyle \mathbb {Z} ^{d}\times \mathbb {R} ^{k}}$ ${\displaystyle 2^{d}(k+1)}$