Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-726
Main Title: Extremal Constructions for Polytopes and Spheres
Translated Title: Extremale Konstruktionen für Polytope und Sphären
Author(s): Pfeifle, Julian
Advisor(s): Ziegler, Günter M.
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Teil I: Polytope dieser Dissertation kreist um die Frage, ob es für jedes n > d >= 4 eine lineare Zielfunktion f:R^d o R und ein d-dimensionales Polytop P mit n Facetten und maximal vielen Ecken gibt, so dass f auf P einen strikt aufsteigenden Hamiltonpfad induziert. Diese Frage ist unter anderem motiviert durch die Existenz der Klee-Minty-Würfel: das sind Polytope vom gleichen kombinatorischen Typ wie ein d-dimensionaler Würfel, die aber so in R^d realisiert sind, dass es einen strikt aufsteigenden Pfad durch alle 2^d Ecken gibt. Sie sind für die Theorie der linearen Programmierung deswegen interessant, weil sie den Simplex-Algorithmus mit einigen natürlichen Pivot-Regeln dergestalt in die Irre leiten, dass er das Optimum erst nach Durchlaufen sämtlicher Ecken des Würfels erreicht. Nun kennen wir in jeder Dimension d die Polytope mit maximal vielen Ecken, bei gegebener Facettenzahl: die polar-nachbarschaftlichen Polytope. Es stellt sich somit die Frage, ob man für alle n > d >= 4 ein polar-nachbarschaftliches d-dimensionales Polytop mit n Facetten so im R^d realisieren kann, dass es einen strikt aufsteigenden Hamiltonpfad zulässt. In Dimension d=4 können wir diese Frage vollständig lösen. In Kapitel 4 betrachten wir den Graphen G des kleinsten interessanten 4-dimensionalen polar-nachbarschaftlichen Polytops C_4(7)^Delta , und klassifizieren sämtliche Äquivalenzklassen von G unter Graphenisomorphie nach ihrer Realisierbarkeit. Insbesondere finden wir auch nichtrealisierbare Orientierungen, was zeigt, dass ein Resultat von Mihalisin und Klee bestmöglich ist. In Kapitel 5 realisieren wir dann für jedes n >= 5 ein 4-dimensionales polar-nachbarschaftliches Polytop mit n Facetten und der maximal möglichen Anzahl n(n-3)/2 von Ecken so im R^4 , dass es bezüglich der linearen Zielfunktion f: R^4 o R, xmapsto x_4 einen strikt aufsteigenden Hamiltonpfad in seinem Graphen gibt. In Teil II: Sphären widmen wir uns mehr kombinatorischen Eigenschaften von Simplizialkomplexen, insbesondere der Frage nach der Anzahl kombinatorischer Typen von simplizialen Sphären. Kalai zeigte im Jahr 1988, dass es für alle d >= 4 deutlich mehr kombinatorische Typen d-dimensionaler simplizialer Sphären als Typen von (d+1)-dimensionalen Polytopen gibt, konnte diese Frage aber für d=3 nicht entscheiden. Wir zeigen in Kapitel 8, dass Kalais Konstruktion für d=3 sogar ausschließlich polytopale Sphären liefert, indem wir sämtliche Sphären seiner Familie als Randkomplexe simplizialer 4-dimensionaler Polytope realisieren. In Kapitel 9 zeigen wir dann, dass die Antwort für d=3 trotzdem dieselbe wie für d >= 4 ist: Es gibt tatsächlich viel mehr kombinatorische Typen von 3-Sphären als von 4-Polytopen! Günter M. Ziegler und ich konstruieren ''viele triangulierte 3-Sphären'', indem wir eine Konstruktion von Heffter aus dem Jahr 1898 mit einer Idee von Eppstein, Kuperberg und Ziegler von 2002 kombinieren. In Kapitel 10 schließlich wird gezeigt, dass es für alle geraden d >= 4 und ungeraden d >= 11 keine d-dimensionalen zentralsymmetrischen sternförmigen Sphären mit 2d+4 Ecken gibt.
The first theme of Part I: Polytopes is the monotone upper bound problem for polytopes: For a d-dimensional polytope with n facets, what is the maximal number of vertices in a monotone path? Chapter 3 contains a proof that the unique 4-polytope with 7 facets and the maximal number 14 of vertices combinatorially admits 7 equivalence classes of orientations of its graph that contain a directed Hamiltonian path and satisfy the AOF and Holt-Klee conditions, and that exactly 3 of these are realizable. In particular, this shows that the Mihalisin-Klee result is best possible: the AOF Holt-Klee criteria are necessary but not sufficient in dimensions higher than three. We also find realizations of ascending Hamiltonian paths on 4-polytopes with 8 facets and the maximal number 20 of vertices. Chapter 4 constructs, for every n >= 5, a realization of a 4-dimensional polytope with n facets and the maximal possible number of vertices (according to McMullen's Upper Bound Theorem) that admits a strictly ascending Hamiltonian path along edges (with respect to some linear objective function). This proves that in dimension 4, there exists an infinite family of polytopes with maximally many vertices on which the simplex algorithm for linear programming may take a detour through all of them before finding the optimum. Part II: Spheres is concerned with extremal constructions for spheres. The starting point for these investigations was the 1988 paper of Kalai in which he constructed a large family of d-dimensional simplicial PL spheres on n vertices for d >= 3. Chapter 8 proves that in dimension 3, Kalai's construction does not produce interesting spheres: ''Kalai's squeezed 3-spheres are polytopal''. These spheres are realized as boundary complexes of convex 4-polytopes by adapting the technique used by Billera and Lee in their proof of the sufficiency of McMullen's conditions in the g-Theorem. Chapter 9 contains a construction (in joint work with Gnter M. Ziegler) for ''many triangulated 3-spheres'': By combining a venerable construction by Heffter from 1898 with a modern idea by Eppstein, Kuperberg and Ziegler from 2002, we construct 2^{Omega(n^{5/4})} simplicial 3-spheres on n vertices. This finally proves that for large n, there exist far more simplicial 3-spheres than 4-polytopes. Chapter 10 is concerned with a special class of ''star-shaped spheres'', namely, centrally symmetric (nearly) neighborly fans. It was already proved by Grnbaum that there is no nearly neighborly centrally symmetric 4-polytope on 12 or more vertices; however, Jockusch and (more explicitly) Lutz constructed infinite series of centrally symmetric nearly neighborly 3-spheres. Using McMullen and Shephard's technique of centrally symmetric Gale diagrams, it is proved that there are no nearly neighborly centrally symmetric d-fans on 2d+4 rays, in even dimension d >= 4 and odd dimension d >= 11.
URI: urn:nbn:de:kobv:83-opus-6279
http://depositonce.tu-berlin.de/handle/11303/1023
http://dx.doi.org/10.14279/depositonce-726
Exam Date: 4-Apr-2003
Issue Date: 6-May-2003
Date Available: 6-May-2003
DDC Class: 510 Mathematik
Subject(s): Polytope
triangulierte Sphären
aufsteigende Pfade
Realisierung von Orientierungen
Polytopes
triangulated spheres
monotone paths
realization of orientations
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Publications

Files in This Item:
File Description SizeFormat 
Dokument_33.pdf2.56 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.