Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4795
Main Title: Fano polytopes
Subtitle: On the classification of smooth Fano polytopes and their triangulations
Translated Title: Fano Polytope
Translated Subtitle: über die Klassifikation von glatten Fano Polytopen und deren Triangulierungen
Author(s): Assarf, Benjamin
Advisor(s): Joswig, Michael
Referee(s): Joswig, Michael
Haase, Christian
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Ein Polytop P als Teilmenge von R^d ist die konvexe Hülle endlich vieler Punkte v_1,v_2,..., v_n in R^d. Bei einem Gitterpolytop haben die Ecken von P nur ganzzahlige Einträge. Polytope, und besonders Gitterpolytope, haben eine Vielzahl an Anwendungen. In der Optimierung beispielsweise liegt die Optimallösung eines linearen Programms auf dem Rand eines Polytops. Auch in der diskreten Optimierung spielen Gitterpolytope eine wichtige Rolle, denn die konvexe Hülle aller zulässigen Punkte eines ganzzahligen linearen Programms ist ein Gitterpolytop. Es gibt zahlreiche Polytopklassen, welche in den verschiedensten Bereichen der Mathematik Anwendung finden. In dieser Arbeit beschäftige ich mich mit einer besonderen Klasse von Polytopen, nämlich die der glatten Fano Polytope. Ein Gitterpolytop P heißt Fano Polytop, falls der Ursprung im Inneren des Polytops liegt und die Ecken primitiv sind. Das bedeutet, dass keine Ecke v existiert mit lambda*v ganzzahlig für ein Skalar lambda in (0,1). Ein Gitterpolytop heißt reflexiv falls der Ursprung im Inneren liegt und das polare Polytop auch ein Gitterpolytop ist. Ein glattes Fano Polytop P ist ein Fano Polytop bei dem die Ecken jeder Facette eine Gitterbasis bilden. Da die Struktur von Fano Polytopen nicht zu kompliziert zu sein scheint, haben sie sich als gute Klasse erwiesen um Behauptungen zu überprüfen oder das Verständnis von Sätzen zu fördern. In gewisser Weise sind Fano Polytope "klein" und "stabil". In algebraischer Geometrie stehen reflexive Fano Polytope in Verbindung mit Gorenstein torischen Fano Varietäten. Die torische Varietät X_P eines Polytopes P wird durch den Seitenfächer von P bestimmt. Dieser ist ein polyedrischer Fächer, welcher von allen Seitenflächen von P aufgespannt wird (Ewald oder Cox, Little und Schenck). Viele Eigenschaften lassen sich zwischen torischen Fano Varietäten und reflexiven Fano Polytopen übersetzen. Beispielsweise ist eine torische Varietät X_P genau dann Q-faktoriell wenn das dazugehörige Fano Polytop P simplizial ist; jede Seitenfläche ist ein Simplex. In diesem Fall ist die Picard Zahl von X_P gleich n-d, wobei n die Anzahl der Ecken des d-Polytops P ist. Eine torische Varietät X_P hat höchstens terminale Singularitäten genau dann, wenn das Fano Polytope P terminal ist; der Ursprung und die Ecken sind die einzigen Ganzzahligen Punkte in P. Eine torische Varietät X_P ist eine Manigfaltigkeit genau dann, wenn das Polytop P ein glattes Fano Polytop ist. Eine Konsequenz der Resultate von Hensley oder Lagarias und Ziegler ist, dass es bis auf Gitteräquivalenzen nur endlich viele d-dimensionale Fano Polytope gibt. Demnach ist es natürlich nach einer Klassifizierung solcher Polytope zu fragen. Eine komplette Klassifikation zu erwarten wäre hoffnungslos, da die aktuellen Klassifikationsresultate vermuten lassen, dass die Anzahl an Äquivalenzklassen exponenziell bezüglich der Dimension wächst. Trotzdem gibt es verschiedene Klassifikationen für einige Unterklassen, beispielsweise glatte reflexive Fano Polytope bis Dimension neun (Batyrev, Watanabe and Watanabe, Sato, Kreuzer and Nill, Obro, Lorenz and Paffenholz). Oder simpliziale, terminale und reflexive Fano Polytope mit mehr als 3d-1 Ecken (Casagrande oder Obro). Zusammen mit Michael Joswig und Andreas Paffenholz klassifizierte ich simpliziale, terminale und reflexive Fano Polytope mit 3d-2 Ecken. Solche Resultate helfen nicht nur die Struktur dieser Polytope zu verstehen, sondern sie sind auch nützlich um Beispiele oder Gegenbeispiele für Sätze oder offene Vermutungen zu finden. Selbst wenn es nie eine komplette Klassifikation geben wird, sind solche Zwischenresultate durchaus von Wert. Der Beweis unserer Klassifikation fürte zu einer Vermutung, welche helfen würde die Struktur dieser Unterklasse genauer zu verstehen. Wir sind der Überzeugung, dass glatte Fano Polytope mit 3d-k Ecken, wobei d >> k, in eine Summe von niederdimensionalen Polytopen zerfällt, wobei die Schranke der Dimension~d linear bezüglich k ist. In einer gemeinsamen Arbeit mit Benjamin Nill wurde der qualitative Teil dieser Behauptung mit einer quadratischen Schranke für d in Abhängigkeit von~k gezeigt. Diese neue Art von Resultat hilft die Struktur der Fano Polytope besser zu verstehen. Die Klasse der Fano Polytope findet viele Anwendungen. Beispielsweise helfen sie untere Schranken für reelle Nullstellen von Wronskisystemen, einer speziellen Art von polynomialen Systemen, zu finden. Soprunova und Sottile zeigten, dass unter bestimmten Voraussetzungen die Signatur einer faltbaren Triangulierung eines Polytops eine untere Schranke zum dazugehörigen Wronskisystem liefert. Dies bedeutet, dass Polytope mit faltbaren Triangulierungen mit einer positiven Signatur von besonderem Interessse sind. Doch solche Polytope sind nicht leicht zu finden. Es stellt sich raus, dass es sich lohnt glatte Fano Polytope mit genauer zu untersuchen, da sie oft solche speziellen Triangulierungen besitzen. In diesem Kontext ist es erstrebenswert den Sekundärfächer dieser Polytopklasse zu charakterisieren, da der Sekundärfächer alle möglichen regulären Triangulierungen kodiert. Eine Konsequenz der oben genannten Klassifikationsresultate ist, dass man zuerst die Triangulierungen der direkten Summe von zwei Polytopen verstehen muss. Insbesondere ist folgende Frage von Interesse: Falls man alle Triangulierungen von zwei Polytopen kennt, ist es möglich alle Triangulierungen der direkten Summe dieser beiden Polytope zu beschreiben? Und falls ja, wie sieht so eine Beschreibung aus? Diese Frage wird positiv beantwortet, allerdings nicht nur für Polytope sondern für (fast) beliebige Punktkonfigurationen. Um all diese theoretischen Resultutate für die oben genannten Anwendungen zu benutzen, braucht man geeignete mathematische Software. Schon allein die große Anzahl an 8.229.721 glatten Fano Polytopen in Dimension neun, macht dies notwendig. Sobald man mit Polytopen und ihren Triangulierungen arbeitet, stößt man auf zwei wichtige Problemstellungen. Zum Einen die Berechnung der konvexen Hülle einer Punktmenge und zum Anderen das Enummerieren von Gitterpunkten in einem Polytop. Obwohl diese zwei Probleme als schwer gelten, gibt es hierfür einige gute Algorithmen. Der zweite Teil dieser Arbeit widmet sich diesen Problemstellungen und den meist genutzen Implementierungen. In einer gemeinsamen arbeit mit Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz and Thomas Rehn benutzen wir polymake zum Untersuchen und Vergleichen des aktuellen Stands der Technik zum Lösen dieser Probleme.
A polytope P as a subset of R^d is the convex hull of finitely many points v_1,v_2,..., v_n in R^d. For lattice polytopes the vertices of P are in the lattice Z^d. Polytopes, and especially lattice polytopes, have a wide variety of applications. For example in optimization the optimal solution of a linear program lies on the boundary of a polytope. When talking about discrete optimization, lattice polytopes are significant since the convex hull of all feasible points of an integer linear program is a lattice polytope. There are numerous classes of polytopes with applications in various fields of mathematics. In this work I will discuss one particular class, namely the class of smooth Fano polytopes. A lattice polytope P is called a Fano polytope if the origin lies in the interior and the vertices are primitive, meaning that for every vertex v there exists no scalar lambda in (0,1) with lambda*v in Z^d. We call a lattice polytope reflexive if it contains the origin as an interior point and its polar polytope is also a lattice polytope. We say that P is a smooth Fano polytope if P is Fano and the vertices of each facet form a lattice basis. In general Fano polytopes have proven themselves to be a good class of polytopes to check conjectures or to understand theorems since their structure seems not to be too complex. To some degree they are "small" and "rigid". In algebraic geometry, reflexive Fano polytopes correspond to Gorenstein toric Fano varieties. The toric variety X_P of a polytope P is determined by the face fan of P, that is, the polyhedral fan spanned by all faces of P (Ewald or Cox, Little, and Schenck). There are several properties which can be translated between toric Fano varieties and reflexive Fano polytopes. For example a toric variety X_P is Q-factorial if and only if the Fano polytope P is simplicial, i.e. each face is a simplex. In this case the Picard number of X_P equals n-d, where n is the number of vertices of a d-dimensional polytope P. The toric variety X_P has at most terminal singularities if and only if the Fano polytope is terminal, that is if the origin and the vertices are the only lattice points in P. The variety X_P is a manifold if and only if the polytope P is smooth Fano. It is a consequence of results of Hensley or Lagarias and Ziegler that there are, up to lattice equivalence, only finitely many d-dimensional Fano polytopes. Therefore, it is only natural to ask for a classification of those polytopes. To aim at a complete classification would be quite hopeless, since the smaller classification results let believe that the number of equivalence classes grow exponentially with respect to the dimension. But there are several classification results for subclasses, e.g. smooth reflexive Fano polytopes up to dimension nine (Batyrev, Watanabe and Watanabe, Sato, Kreuzer and Nill, Obro, Lorenz and Paffenholz), or simplicial, reflexive and terminal Fano polytopes with more than 3d-1 vertices (Casagrande, Obro). In joined work with Michael Joswig and Andreas Paffenholz we classified those polytopes with 3d-2 vertices. Such classification results do not only help understanding their structure, they also help finding examples or counterexamples for theorems and open conjectures. So even if there won't be a complete classification, those intermediate results are valuable. The proof of our classification leads to a conjecture, which would help understanding the nature of this subclass. We believe that smooth Fano polytopes with 3d-k vertices and d >> k decompose into a sum of lower dimensional polytopes, where the bound on the dimension d is linear with respect to k. In joined work with Benjamin Nill we showed the qualitative part of that conjecture, with a quadratic bound on d with respect to k. This is a new kind of structural result for Fano polytopes. Moreover, Fano polytopes can be used for various applications. For example they help finding lower bounds for the number of real roots of Wronski systems, which are special polynomial systems. Soprunova and Sottile showed, that under certain circumstances the signature of a foldable triangulation of a polytope yields a lower bound for the number of real roots of the corresponding Wronski system. This means that polytopes which have a foldable triangulation with a signature greater than one are of special interest. But those are not easy to find. It turns out that smooth Fano polytopes are a well suited subclass to take a closer look at, because they often acquire such triangulations. For this application, classifying the secondary fans of those polytopes would be a goal, as the secondary fan of a polytope encodes all possible regular triangulations. A consequence of the classification results mentioned above is that the triangulations of the direct sum of two polytopes need to be understood first. In particular, the following question is of interest: If all triangulation of two polytopes are known, is it possible to describe all triangulations of the direct sum of those polytopes? If it is possible, how would such a description look like? This will be answered positively, not only for polytopes but also for (almost) arbitrary point configurations. In order to use all these theoretical results for many of the mentioned applications, one needs mathematical software. The large number of 8,229,721 smooth Fano polytopes in dimension nine alone makes it necessary to use suitable software. The computation of the convex hull of a set of points, and the enumeration of lattice points inside a polytope are two important problems one faces when dealing with polytopes or their triangulations. Although those two problems are considered to be hard, there exist several good implementations. The second part of this work is dedicated to these problems and the most commonly used implementations. In a joined work with Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz and Thomas Rehn, we use the software polymake to investigate and discuss the state of the art of these implementations.
URI: urn:nbn:de:kobv:83-opus4-73571
http://depositonce.tu-berlin.de/handle/11303/5092
http://dx.doi.org/10.14279/depositonce-4795
Exam Date: 23-Oct-2015
Issue Date: 30-Oct-2015
Date Available: 30-Oct-2015
DDC Class: 510 Mathematik
Subject(s): Direkte Summe
Fano Polytope
Gitterpunktenumeration
Konvexe Hülle
Triangulierungen
Convex hull
Direct sum
Fano polytopes
Triangulations
Creative Commons License: https://creativecommons.org/licenses/by-sa/3.0/de/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
assarf_benjamin.pdf52,23 MBAdobe PDFThumbnail
View/Open


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