Теорема Дуаньона

Теорема Дуаньона в геометрии является аналогом теоремы Хелли для целочисленной решетки . Он утверждает, что в если $d$-мерное евклидово пространство обладает тем свойством, что пересечение всех $2^{d}$ содержит целую точку, то пересечение всех множеств содержит целую точку. Поэтому, $d$-мерные целочисленные линейные программы образуют задачу типа ЛП комбинаторной размерности. $2^{d}$, и может быть решено с помощью определенных обобщений алгоритмов линейного программирования за время, линейное по количеству ограничений задачи и управляемое с фиксированными параметрами по ее размерности. Та же самая теорема применима в более общем плане к любой решетке , а не только к целочисленной решетке.

Теорему можно отнести к выпуклой геометрии , дискретной геометрии и геометрии чисел . Она названа в честь бельгийского математика и математического психолога Жана-Поля Дуаньона, опубликовавшего ее в 1973 году. Дуаньон благодарит Фрэнсиса Бюкенхаута за постановку вопроса, на который отвечает эта теорема. Ее также называют теоремой Дуаньона–Белла–Скарфа . отдавая должное экономистам-математикам Дэвиду Э. Беллу и Герберту Скарфу , которые оба заново открыли его в 1977 году. и указал на его применение в целочисленном программировании.

Результат однозначен: существуют системы полупространств , для которых каждое $2^{d}-1$ имеют целочисленную точку в своем пересечении, но для которой вся система не имеет целочисленного пересечения. Такую систему можно получить, например, выбрав полупространства, содержащие все вершины единичного куба, кроме одной . Другой способ сформулировать результат состоит в том, что число Хелли выпуклых подмножеств целых чисел в точности равно $2^{d}$. В более общем смысле, число Хелли любого дискретного набора евклидовых точек равно максимальному количеству точек, которые можно выбрать для формирования вершин выпуклого многогранника , который не содержит других точек из этого набора. Обобщая как теорему Хелли, так и теорему Дуаньона, число Хелли декартова произведения $\mathbb {Z} ^{d}\times \mathbb {R} ^{k}$ является $2^{d}(k+1)$.