TY - GEN A1 - Grötschel, Martin A1 - Henk, Martin T1 - On the Representation of Polyhedra by Polynomial Inequalities N2 - A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$. T3 - ZIB-Report - 02-15 KW - polyhedra and polytopes KW - semialgebraic sets KW - polyhedral combinatorics KW - polynomial inequalities Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6826 ER - TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities. T3 - ZIB-Report - 04-53 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8284 ER - TY - GEN A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial Inequalities Representing Polyhedra N2 - Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities. T3 - ZIB-Report - 03-25 KW - polyhedra and polytopes KW - semi-algebraic sets KW - polyhedral combinatorics KW - polynomial inequalities KW - stability index Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7473 ER - TY - GEN A1 - Bruns, Winfried A1 - Gubeladze, Joseph A1 - Henk, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - A counterexample to an integer analogue of Caratheodorys theorem N2 - For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed. T3 - ZIB-Report - SC-98-28 KW - Integral pointed cones KW - Hilbert basis KW - integral Carathéodory property Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3718 ER - TY - JOUR A1 - Bosse, Hartwig A1 - Grötschel, Martin A1 - Henk, Martin T1 - Polynomial inequalities representing polyhedra JF - Mathematical Programming Y1 - 2005 U6 - https://doi.org/10.1007/s10107-004-0563-2 VL - 103 IS - 1 SP - 35 EP - 44 ER - TY - JOUR A1 - Grötschel, Martin A1 - Henk, Martin T1 - The Representation of Polyhedra by Polynomial Inequalities JF - Discrete & Computational Geometry Y1 - 2003 U6 - https://doi.org/10.1007/s00454-003-0782-y VL - 29 IS - 4 SP - 485 EP - 504 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Test sets of the knapsack problem and simultaneous diophantine approximation N2 - This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem. T3 - ZIB-Report - SC-97-13 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2825 ER - TY - GEN A1 - Böröczky, Karoly A1 - Henk, Martin T1 - Random Projections of Regular Polytopes N2 - Based on an approach of Affentranger&Schneider we give an asymptotic formula for the expected number of $k$-faces of the orthogonal projection of a regular $n$-crosspolytope onto a randomly chosen isotopic subspace of fixed dimension, as $n$ tends to infinity. In particular, we present a precise asymptotic formula for the (spherical) volume of spherical regular simplices, which generalizes Daniel's formula. T3 - ZIB-Report - SC-97-21 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2903 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Henk, Martin T1 - On a series of Gorenstein cyclic quotient singularities admitting a unique projective crepant resolution. N2 - Let $G$ be a finite subgroup of SL$\left( r,% {\mathbb{C}}\right) $. In dimensions $r=2$ and $r=3$, McKay correspondence provides a natural bijection between the set of irreducible representations of $G$ and a cohomology-ring basis of the overlying space of a projective, crepant desingularization of ${\mathbb{C}}^r/G$. For $r=2$ this desingularization is unique and is known to be determined by the Hilbert scheme of the $G$% -orbits. Similar statements (including a method of distinguishing just {\it{one}} among all possible smooth minimal models of ${\mathbb{C}}^3/G$), are very probably true for all $G$'s $\subset $ SL$\left( 3,{\mathbb{C}}\right) $ too, and recent Hilbert-scheme-techniques due to Ito, Nakamura and Reid, are expected to lead to a new fascinating uniform theory. For dimensions $r\geq 4 $, however, to apply analogous techniques one needs extra modifications. In addition, minimal models of ${\mathbb{C}}^r/G$ are smooth only under special circumstances. ${\mathbb{C}}^4/\left( \hbox{\rm involution}\right) $, for instance, cannot have any smooth minimal model. On the other hand, all abelian quotient spaces which are c.i.'s can always be fully resolved by torus-equivariant, crepant, projective morphisms. Hence, from the very beginning, the question whether a given Gorenstein quotient space ${\mathbb{C}}% ^r/G$, $r\geq 4$, admits special desingularizations of this kind, seems to be absolutely crucial.\noindent In the present paper, after a brief introduction to the existence-problem of such desingularizations (for abelian $G$'s) from the point of view of toric geometry, we prove that the Gorenstein cyclic quotient singularities of type \[ \frac 1l\,\left( 1,\ldots ,1,l-\left( r-1\right) \right) \] with $l\geq r\geq 2$, have a \textit{unique }torus-equivariant projective, crepant, partial resolution, which is full'' iff either $l\equiv 0$ mod $% \left( r-1\right) $ or $l\equiv 1$ mod $\left( r-1\right) $. As it turns out, if one of these two conditions is fulfilled, then the exceptional locus of the full desingularization consists of $\lfloor\frac{l}{r-1} \rfloor $ prime divisors, $\lfloor\frac{l}{r-1} \rfloor -1$ of which are isomorphic to the total spaces of ${\mathbb{P}}_{{\mathbb{C}}}^1$-bundles over ${\mathbb{P}}_{{\mathbb{C}}% }^{r-2}$. Moreover, it is shown that intersection numbers are computable explicitly and that the resolution morphism can be viewed as a composite of successive (normalized) blow-ups. Obviously, the monoparametrized singularity-series of the above type contains (as its first member'') the well-known Gorenstein singularity defined by the origin of the affine cone which lies over the $r$-tuple Veronese embedding of ${\mathbb{P}}_{\mathbb{C}}^{r-1}$. T3 - ZIB-Report - SC-97-39 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3084 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Henk, Martin A1 - Ziegler, Günter M. T1 - All Abelian Quotient C.I.-Singularities Admit Projective Crepant Resolutions in All Dimensions N2 - \def\Bbb{\mathbb} For Gorenstein quotient spaces $\Bbb{C}^d/G$, a direct generalization of the classical McKay correspondence in dimensions $d\geq 4$ would primarily demand the existence of projective, crepant desingularizations. Since this turned out to be not always possible, Reid asked about special classes of such quotient spaces which would satisfy the above property. We prove that the underlying spaces of all Gorenstein abelian quotient singularities, which are embeddable as complete intersections of hypersurfaces in an affine space, have torus-equivariant projective crepant resolutions in all dimensions. We use techniques from toric and discrete geometry. T3 - ZIB-Report - SC-97-01 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2708 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations N2 - This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem. T3 - ZIB-Report - SC-97-29 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2989 ER - TY - GEN A1 - Dais, Dimitrios I. A1 - Haus, Utz-Uwe A1 - Henk, Martin T1 - On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities N2 - \noindent An immediate generalization of the classical McKay correspondence for Gorenstein quotient spaces $\Bbb{C}^{r}/G$ in dimensions $r\geq 4$ would primarily demand the existence of projective, crepant, full desingularizations. Since this is not always possible, it is natural to ask about special classes of such quotient spaces which would satisfy the above property. In this paper we give explicit necessary and sufficient conditions under which 2-parameter series of Gorenstein cyclic quotient singularities have torus-equivariant resolutions of this specific sort in all dimensions. T3 - ZIB-Report - SC-98-12 Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3559 ER - TY - GEN A1 - Awyong, Poh Wah A1 - Henk, Martin A1 - Scott, Paul R. T1 - Note on lattice-point-free convex bodies N2 - We prove inequalities relating the inradius of a convex body with interior containing no point of the integral lattice, with the volume or surface area of the body. These inequalities are tight and generalize previous results. T3 - ZIB-Report - SC-96-44 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2546 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - On Hilbert bases of polyhedral cones N2 - For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates. T3 - ZIB-Report - SC-96-12 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2230 ER -