Loading…
Linear constraints on Face numbers of Polytopes
Linear constraints on Face numbers of Polytopes
Werner, Axel
Inst. Mathematik
Polytope sind zentrale Objekte der Geometrie, die man unter verschiedensten Aspekten betrachten kann. In dieser Arbeit liegt der Schwerpunkt auf der kombinatorischen Sicht, wobei das Ziel ist, Aussagen über den f-Vektor, bzw. den Fahnenvektor (flag vector) eines Polytops zu machen. Ersterer gibt die Anzahlen der Seiten jeweiliger Dimension im Polytop an, zweiterer allgemeiner die Anzahlen der Ketten (oder Fahnen) von Seiten. Das wesentliche offene Problem dabei ist, die möglichen f- bzw. Fahnenvektoren aller Polytope zu charakterisieren. Dies wurde für den 3-dimensionalen Fall von Steinitz (1906) gelöst, für höhere Dimensionen scheint das Problem jedoch wesentlich schwieriger zu sein. Bekannt sind viele notwendige Eigenschaften für f- und Fahnenvektoren, die meisten davon lineare Restriktionen. Die affine Hülle der Menge aller f- bzw. Fahnenvektoren von Polytopen wurde von Bayer und Billera (1985) vollständig bestimmt. Affine Ungleichungen beschreiben eine lineare Approximation der konvexen Hülle der besagten Menge. Um zu klären, wie genau man damit f- bzw. Fahnenvektoren beschreibt, sind Beispiele und Konstruktionen von Polytopen mit extremalen Eigenschaften anzugeben, deren f- bzw. Fahnenvektoren möglichst viele Ungleichungen mit Gleichheit erfüllen. In Kapitel 1 wird nach kurzer Einführung der grundlegenden Definitionen und Notation ein Überblick über die verwendeten bekannten Resultate und Techniken gegeben, die sowohl geometrischer, als auch kombinatorischer Natur sind. Kapitel 2 untersucht elementar wie durch sukzessives Hinzufügen von Ecken Polytope beschrieben werden können. Im Allgemeinen ist jedoch die Anzahl von auftretenden Möglichkeiten viel zu groß um sinnvolle Aussagen machen zu können, weshalb wir uns auf einige Spezialfälle beschränken. Dies ist einerseits die Stacking-Operation, andererseits eine Verallgemeinerung davon, das Pseudostacking. In beiden Fällen beschreiben wir, wie sich f- und Fahnenvektoren durch die jeweilige Operation ändern. Zwei konkrete Basen von Polytopen werden zunächst in Kapitel 3 besprochen, die von Kalai (1988) und die von Bayer und Billera (1985). Für zweitere zeigen wir, dass deren Fahnenvektoren das ganzzahlige Gitter der entsprechenden Dimension aufspannen, eine leichte Verschärfung der Basiseigenschaft. Im Anschluss stellen wir eine Methode zur Visualisierung von f- und Fahnenvektoren vor, eine Verallgemeinerung der Darstellung von Ziegler (2002) für f-Vektoren von 4-Polytopen. Abschließend illustrieren wir dieses Vorgehen am Beispiel des oben erwähnten Satzes von Steinitz und charakterisieren darüberhinaus die f-Vektoren von zentralsymmetrischen 3-Polytopen. Kapitel 4 beschäftigt sich mit Fahnenvektoren von 4-Polytopen. Wir diskutieren anhand einer neuen Version der Darstellung von Bayer (1987) die bekannten und neuen Ergebnisse. Zwei neue Konstruktionen werden vorgestellt, die Pseudostacking bzw. nachbarschaftlich kubische Polytope von Joswig und Ziegler (2000) verwenden. Dies erlaubt den Schluss, dass keine der bekannten Ungleichungen verbessert werden kann, trotzdem aber noch Raum für offene Fragen und Vermutungen bleibt, die wir beleuchten. In Kapitel 5 werden spezielle Ungleichungen für den Fahnenvektor betrachtet, die aus der Basis von Kalai, sowie aus Überlegungen von Braden zum g-Vektor hervorgehen. Wir können genauere Aussagen zu einigen der Ungleichungen in beliebig hoher Dimension machen und geben eine vollständige Beschreibung der Situation bis Dimension 6. In Kapitel 6 sind einige Ergebnisse zu f-Vektoren zusammengefasst. Einerseits widmen wir uns der Visualisierung von f-Vektoren von 4- und 5-Polytopen, andererseits der Frage nach der Unimodalität und ähnlicher Eigenschaften, wobei wir einige Ergebnisse und Gegenbeispiele in Dimensionen bis 7 angeben. Zusätzlich behandeln wir die sogannte 3^d-Vermutung von Kalai (1989), die wir für Dimension 4 beweisen und deren diverse Verstärkungen im Wesentlichen widerlegt werden. Dabei stoßen wir auf interessante Beispiele, die weitere Untersuchungen erstrebenswert erscheinen lassen. Schließlich widmen wir uns im letzten Kapitel 7 Schälungen und benutzen diese, um kleine 2-einfache, 2-simpliziale Polytope zu untersuchen. Darüberhinaus beschreiben wir einen experimentellen Algorithmus, sowie dessen Implementation, mit dem kleine Polytope mit Hilfe von Schälungen enumeriert werden können.
Polytopes are central objects in geometry and can be studied from a variety of viewpoints. This thesis is concerned about combinatorial properties of polytopes and aims at statements about the f-vector, respectively flag vector, of a polytope. The former counts the number of faces of the polytope of different dimensions, the latter the number of chains (or flags) of faces. The big open problem in this respect is to characterise the possible f-, resp. flag vectors, of all polytopes. This problem has been solved by Steinitz (1906) for the 3-dimensional case, but for higher dimensions it seems to be much more difficult. A number of necessary conditions are known for f- and flag vectors, most of them linear constraints. Bayer and Billera (1985) completely described the affine hull of the set of all f-, resp. flag vectors, of polytopes. Using affine inequalities one can give a linear approximation of the convex hull of this set. To find out how good this approximation is, one has to construct examples of polytopes with extremal properties, that is, polytopes such that as many of the given inequalities as possible are tight at their f-, resp. flag vectors. Chapter 1 first gives a short introduction to the basic definitions and notation, and afterwards presents an overview over known results and techniques---both of geometric, as well as combinatorial flavour---that are used throughout the thesis. In Chapter 2 we analyse an elementary method to describe a polytope by successively adding its vertices. In general, the number of possible configurations is far to high to make useful statements. Therefore we confine ourselves to special cases: on the one hand the well-known stacking operation, and on the other hand a generalisation of this, which we call pseudostacking. In both cases we describe how f- and flag vectors change when the respective operation is applied. Two specific bases of polytopes are described in Chapter 3, one of them due to Kalai (1988), the other given by Bayer and Billera (1985). For the latter we show that their flag vectors span the integer lattice in the corresponding dimension, which is a slightly stronger statement than given in the original paper. Following, we give a method to visualise f- and flag vectors, which generalises the presentation of Ziegler (2002) for f-vectors of 4-polytopes. Finally, we illustrate this general recipe with Steinitz' theorem (see above) and additionally characterise the f-vectors of centrally-symmetric 3-polytopes. Chapter 4 deals with flag vectors of 4-polytopes. We discuss a new version of the depiction of Bayer (1987), as well as the known and the new results connected to it. Two new constructions are presented, which use pseudostacking, and the neighbourly cubical polytopes due to Joswig and Ziegler (2000), respectively. This allows the conclusion that none of Bayer's inequalities can be improved. However, there still remain open questions and conjectures to mention. In Chapter 5 special inequalities for flag vectors are discussed which arise from Kalai's basis and considerations about the g-vector due to Braden. We give statements for some of these inequalities in arbitrarily high dimension, and a complete description of the situation up to dimension 6. Chapter 6 gathers some results concerning f-vectors. We first visualise f-vectors of 4- and 5-polytopes, according to the method given above. Then we address the problem of unimodality and similar properties, where we present some results and counterexamples in dimensions up to 7. Additionally, we discuss the so-called 3^d-conjecture of Kalai (1989), prove it for dimension 4, and give counterexamples to some stronger conjectures. Here a number of interesting examples show up which suggest further investigations. Finally, in Chapter 7, we introduce shellings and use them to study small 2-simple, 2-simplicial polytopes. Furthermore, we describe an experimental algorithm and its implementation which allows for the enumeration of small polytopes using shellings.
