Polytopes with few coordinate values: combinatorial types and diameter bounds

Abstract

In this thesis we introduce (0,1,a)- and (0,1,a_i)-polytopes and explore their various combinatorial properties. These polytopes are generalizations of (0,1)-polytopes, which arise as fundamental objects of combinatorial optimization and linear programming. While $(0,1)$-polytopes can be described by having two distinct vertex coordinate values, (0,1,a)- and (0,1,a_i)-polytopes are allowed three. This thesis focuses on the combinatorial structures that result from this constraint relaxation. In the first chapter we define (0,1,a)- and (0,1,a_i)-polytopes and give interesting examples which motivate the thesis and provide intuition into their geometric and combinatorial structures. In particular, we give examples of combinatorial types of polytopes that distinguish the classes of rational and irrational polytopes, as well as (0,1,a)- and (0,1,a_i)-polytopes. In the second chapter we fully enumerate the rational (0,1,a)-polytopes in dimension three. In order to do so, we find an upper bound on the number of vertices such a polytope may have, as well as a finite set of a values that suffice to produce all combinatorial types. We then discuss the complexity of a full enumeration of (0,1,a)- and (0,1,a_i)-polytopes in dimension three and four. The third chapter studies extremal properties of (0,1,a)-polytopes, which lead to the intractability of enumerations in higher dimensions. We find a set of a values from which all combinatorial types of (0,1,a)-polytopes arise; its size grows exponentially with the dimension. This method has also led to a particular nice family of (0,1)-matrices whose set of integral determinants grows exponentially with dimension. In the fourth chapter we provide a tight upper bound on the diameter of (0,1,a_i)-polytopes. Further, we provide an algorithm that finds a path between any two vertices in linear time.

In der vorliegenden Arbeit stellen wir (0, 1, a)- und (0, 1, a i )-Polytope vor und erforschen ihre verschiedenen kombinatorischen Eigenschaften. Diese Poly- tope sind Verallgemeinerungen von (0, 1)-Polytopen, die fundamentale Objekte der kombinatorischen Optimierung und linearen Programmierung darstellen. Während (0, 1)-Polytope durch Ecken mit zwei verschiedenen Koordinaten- werten beschrieben werden, sind (0, 1, a)- und (0, 1, a i )-Polytope durch Ecken mit drei verschiedenen Koordinatenwerten characterisiert. Diese Dissertation konzentriert sich auf die durch diese Verallgemeinerung entstehenden neuen kombinatorischen Strukturen. Im ersten Kapitel werden diese Polytope definiert und interessante Beispiele präsentiert, die sowohl die vorliegende Arbeit motivieren sollen, als auch Intu- ition für die neuen geometrischen und kombinatorischen Strukturen vermitteln sollen. Insbesondere geben wir Beispiele an, die zeigen, dass sich die kom- binatorischen Typen von (0, 1, a)- und (0, 1, a i )-Polytopen mit ganzzahligen, rationalen und irrationalen Koordinaten jeweils unterscheiden können. Im zweiten Kapitel werden dreidimensionale (0, 1, a)-Polytope mit ratio- nalen Koordinaten vollständig enumeriert. Hierfür wird in einem ersten Schritt die maximale Anzahl an Ecken, die ein solches Polytop haben kann, nach oben beschränkt. In einem zweiten Schritt wird gezeigt, dass nur endlich viele Werte von a zu verschiedenen kombinatorischen Typen führen. Im Anschluss daran diskutieren wir die Komplexität der Enumeration der kombinatorischen Typen aller (0, 1, a)- und (0, 1, a i )-Polytope in den Dimensionen drei und vier. Das dritte Kapitel behandelt extremale Eigenschaften von (0, 1, a)-Poly- topen, die dazu führen, dass Enumerationen in höheren Dimensionen nicht mehr möglich sind. In diesem Zusammenhang definieren wir eine Menge von Werten a mit exponentiell wachsender Kardinalität, sodass verschiedene Werte a zu Polytopen mit verschiedenen kombinatorischen Typen führen können. Diese Methode führt ebenfalls zu einer besonders schönen exponentiell wach- senden Klasse von (0, 1)-Matritzen, deren Determinanten alle ganzzahlig sind. Im vierten Kapitel diskutieren wir den Durchmesser von (0, 1, a i )-Polytopen und geben insbesondere eine lineare obere Schranke an. Wir präsentieren einen Algorithmus, der in linearer Zeit zwischen je zwei Ecken einen kurzen Weg findet.