TY - GEN A1 - Rambau, Jörg T1 - Triangulierungen von Punktmengen und Polyedern N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung ü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ührende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung. T3 - ZIB-Report - 00-46 KW - point configuration KW - triangulation KW - polytope KW - polyhedron KW - Gale diagram KW - secondary polytope KW - cyclic polytope KW - graph of all triangulations KW - conn Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145 ER - 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 - Huber, Birkett A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings N2 - 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. T3 - ZIB-Report - SC-98-44 KW - Polyhedral subdivision KW - fiber polytope KW - mixed subdivision KW - lifting subdivision KW - Minkowski sum KW - Cayley Trick KW - Bohne-Dress Theorem Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3874 ER - TY - THES A1 - Rambau, Jörg T1 - Polyhedral Subdivisions and Projections of Polytopes N2 - 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. N2 - Die vorliegende Dissertation beschäftigt sich mit strukturellen Fragen in der Theorie der polyedrischen Unterteilungen von Punktkonfigurationen. Hierbei sind vor allem globale Eigenschaften der Menge aller Unterteilungen einer gegebenen Punktkonfiguration von Interesse. Eine wichtige ungelöste Frage in diesem Zusammenhang ist die folgende: Ist es immer möglich, von einer beliebigen Triangulierung einer gegebenen Punktkonfiguration zu jeder anderen Triangulierung derselben Konfiguration zu gelangen, indem man sogenannte bistellare Operationen durchführt? Mit anderen Worten, ist die Menge aller Triangulierungen einer gegebenen Punktkonfiguration stets bistellar zusammenhängend? Die Ergebnisse der vorliegenden Doktorarbeit liefern auf zwei Seiten dieser nach wie vor offenen Frage Fortschritte: \begin{itemize} \item Die Menge aller durch eine Polytopprojektion induzierten Unterteilungen ist nicht immer --- in einem verallgemeinerten Sinne --- bistellar zusammenhängend. Dieses Resultat wird durch ein Gegenbeispiel zur sogenannten "Verallgemeinerten Baues Vermutung"' erzielt. \item Die Menge aller Triangulierungen eines zyklischen Polytops bildet eine beschränkte Halbordnung. Die Ueberdeckungsrelationen sind gerichtete bistellare Operationen. Für zyklische Polytope ist die obige Frage nach bistellarem Zusammenhang also positiv beantwortet. \end{itemize} In der Einleitung wird das mathematische Umfeld der betrachteten Strukturen näher beleuchtet: Die "Verallgemeinerte Baues Vermutung" steht in Verbindung mit verschiedensten mathematischen Konzepten, angefangen von kombinatorischen Modellen von Schleifenräumen bis hin zu Diskriminanten von Polynomen in mehreren Variablen. Die Triangulierungs-Halbordnungen von zyklischen Polytopen sind zugleich natürliche Verallgemeinerungen der gut studierten Tamari-Verbände in der Ordnungstheorie. Ausserdem existiert ein Zusammenhang mit den höheren Bruhat-Ordnungen, die ähnliche Struktureigenschaften aufweisen. Ein Nebenprodukt der Untersuchungen ist die Schälbarkeit aller Triangulierungen von zyklischen Polytopen ohne neue Ecken. Das ist um so interessanter, da die meisten Triangulierungen von zyklischen Polytopen nicht-regulär sind. KW - polyedrische Unterteilung KW - Triangulierung KW - Verallgemeinertes Baues-Problem KW - Zyklisches Polytop KW - Höhere Bruhat-Ordnung KW - polyhedral subdivision KW - triangulation KW - Generalized Baues Problem KW - cyclic polytope KW - higher Bruhat order Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10271 SN - 3-8265-1955-8 ER -