@misc{BosseGroetschelHenk2004, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8284}, number = {04-53}, year = {2004}, abstract = {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.}, language = {en} } @misc{HuberRambauSantos1999, author = {Huber, Birkett and Rambau, J{\"o}rg and Santos, Francisco}, title = {The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3874}, number = {SC-98-44}, year = {1999}, abstract = {In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum \$\mathcal{A}_1+\cdots+\mathcal{A}_r\$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding \$\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)\$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.}, language = {en} } @misc{GroetschelHenk2002, author = {Gr{\"o}tschel, Martin and Henk, Martin}, title = {On the Representation of Polyhedra by Polynomial Inequalities}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6826}, number = {02-15}, year = {2002}, abstract = {A beautiful result of Br{\"o}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\$.}, language = {en} } @misc{BosseGroetschelHenk2003, author = {Bosse, Hartwig and Gr{\"o}tschel, Martin and Henk, Martin}, title = {Polynomial Inequalities Representing Polyhedra}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7473}, number = {03-25}, year = {2003}, abstract = {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.}, language = {en} } @misc{Rambau2000, author = {Rambau, J{\"o}rg}, title = {Triangulierungen von Punktmengen und Polyedern}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6145}, number = {00-46}, year = {2000}, abstract = {Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung {\"u}ber Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterf{\"u}hrende Themen regul{\"a}re Triangulierungen, Sekund{\"a}rpolytope, bistellare Operationen, h{\"o}here Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel {\"u}ber Enumeration und Optimierung beschließt die Zusammenstellung.}, language = {de} } @phdthesis{Rambau1996, author = {Rambau, J{\"o}rg}, title = {Polyhedral Subdivisions and Projections of Polytopes}, isbn = {3-8265-1955-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10271}, year = {1996}, abstract = {The present dissertation deals with the structure of polyhedral subdivisions of point configurations. Of particular interest are the global properties of the set of all subdivisions of a given point configuration. An important open problem in this context is the following: can one always transform any triangulation of a given point configuration to any other triangulation of the same configuration by means of bistellar operations? In other words, is the set of all triangulations of a given point configuration always bistellarly connected? The results presented in this thesis contribute progress from two directions. \begin{itemize} \item The set of all subdivisions that are induced by a polytope projection is in general not bistellarly connected in a generalized sense. This result is obtained by constructing a counterexample to the so-called Generalized Baues Conjecture.'' \item The set of all triangulations of a cyclic polytope forms a bounded poset. The covering relations are given by increasing bistellar operations. Thus we get an affirmative answer to the above question in the case of cyclic polytopes. \end{itemize} In the introduction, the mathematical environment of the structures under consideration is illuminated. The "Generalized Baues Conjecture" has connections to various mathematical concepts, such as combinatorial models for loop spaces, discriminants of polynomials in several variables, etc. The triangulation posets of cyclic polytopes are natural generalizations of the well-studied Tamari lattices in order theory. Moreover, there is a connection to the higher Bruhat orders, which have similar structural properties. As a by-product, the investigations yield the shellability of all triangulations of cyclic polytopes without new vertices. This is in particular interesting because most triangulations of cyclic polytopes are non-regular.}, language = {en} }