0/1-Polytope: Typische und Extremale Eigenschaften

0/1-Polytopen kann man in vielen Gebieten der diskreten Mathematik begegnen. Das bekannteste ist als "polyedrische Kombinatorik" bekannt. Auch wenn man die polyedrische Kombinatorik meist mit kombinatorischer Optimierung in Verbindung bringt, gibt es wichtige Zusammenhänge zu anderen Gebieten, zum Beispiel zum Zählen von kombinatorischen Strukturen. Trotz ihres breiten Anwendungsspektrums existiert keine umfassende Theorie über 0/1-Polytope. Es scheint so als seien 0/1-Polytope besonders komplizierte Objekte. Die Ergebnisse, welche in dieser Dissertation dargestellt werden, gruppieren sich um drei Hauptthemen: (1) obere Schranken für die minimale Anzahl von Seiten (Kanten und Facetten), (2) eine Vermutung von Mihail und Vazirani über die Kantenexpansion und (3) zufällige 0/1-Polytope. Zufälligen 0/1-Polytope können aus zwei verschiedenen Blickwinkeln betrachtet werden. Zum einen kann man Zufall benutzen, um die Komplexität allgemeiner 0/1-Polytope zu durchbrechen. Zum anderen kann man untersuchen, welche Eigenschaften zufällige 0/1-Polytope mit hoher Wahrscheinlichkeit besitzen. Dies sind dann typische Eigenschaften von 0/1-Polytopen und können nützlich sein, um Eigenschaften spezieller 0/1-Polytope einzuordnen. Nach einer kurzen Einführung in die Grundlagen der Polytoptheorie und einen Überblick über den aktuellen Stand der Forschung auf dem Gebiet der 0/1-Polytope, werden Grundlagen aus der Wahrscheinlichkeitstheorie kurz eingeführt. Die Ergebnisse zu zufälligen 0/1-Polytopen (3) umfassen: (a) Schwellenwert Resultate mit exponentieller Konvergenz zu der Wahrscheinlichkeit, dass $k$ zufällige Ecken eines zufälligen 0/1-Polytopes eine $(k-1)$-dimensionale Seite bilden; (b) Es gibt 0/1-Polytope mit exponentiell kleiner Eckenexpansion; (c) für jedes $k$ gibt es eine Konstante $c_k$, so dass ein zufälliges 0/1-Polytop in $[0,1]^d$ mit höchstens $2^{cd}$ Ecken sehr wahrscheinlich $k$-nachbarschaftlich ist. Ergebnis (b) zeigt, dass es für die Vermutung von Mihail und Vazirani (2) nicht genügt die Eckenexpansion zu untersuchen. Allerdings scheint es schwierig oder unmöglich zu sein, dieses Negativresultat auf die Kantenexpansion auszuweiten. Ergebnisse (a) und (c) zeigen typische Eigenschaften von zufälligen 0/1-Polytopen. Hieraus lässt sich schließen, dass ein vollständiger Graph für 0/1-Polytope aus der kombinatorischen Optimierung nichts besonderes sind, da diese Polytope meistens nur sub-exponentiell viele Ecken haben. Bekannte Beispiele für 0/1-Polytope aus der kombinatorischen Optimierung sind Traveling Salesman Polytope'' und Cut-Polytope''. Im letzten Kapitel stellen wir revlex-initiale 0/1-Polytope vor. Diese speziellen Knap\-sack-Poly\-tope haben sehr wenige Facetten und Kanten. Wir benutzen diese Polytope, um zu zeigen, dass es in jeder Dimension $d$ und sinnvoller Eckenzahl $n$ ein $d$-dimensionales 0/1-Polytope mit $n$ Ecken gibt, welches höchstens $3d$ Facetten und Eckengrad höchstens $d+8$ hat. Dies sind die ersten Resultate zu oberen Schranken an die minimale Anzahl der Seiten von 0/1-Polytopen (1). Trotz des dünnen Graphen erfüllen diese 0/1-Polytope die Vermutung von Mihail und Vazirani (2). Abschließend betrachten wir noch kurz "erweiterte revlex-initiale 0/1-Polytope", welche eine weiterführende Richtung in der Untersuchung von Knapsack-Polytopen im Hinblick auf die Vermutung von Mihail und Vazirani sein können.0/1-Polytopes appear in many areas of discrete mathematics. The most prominent among them might be polyhedral combinatorics. Although polyhedral combinatorics is often connected with combinatorial optimization there are also important connection to other areas of discrete mathematics such as counting combinatorial objects. Despite their vast area of applications, there is no comprehensive theory of 0/1-polytopes. It seems that 9/1-polytopes are particularly complex objects. The results of this thesis can be divided into three main categories: (1) upper bounds on the minimal number of faces (edges and facets), (2) a conjecture of Mihail and Vazirani, and (3) random 0/1-polytopes. There two ways to view random 0/1-polytopes. randomness can be used to break the complex structure of 0/1-polytopes. On the other hand properties of random 0/1-polytopes can be seen as typical properties of (deterministic) 0/1-polytopes. Typical properties can play an important role to judge results on specific 0/1-polytopes. After a short introduction to the basics of polytope theory and an survey on the state-of-the-art on 0/1-polytopes, a short introduction to probability theory is given. The results on random 0/1-polytopes (3) are among others: (a) threshold results with exponential convergence on the edge probability and the probability that $k$ random vertices build a $k-1$ dimensional face; (b) there are 0/1-polytopes with exponentially small vertex expansion; (c) for every $k$ there is a constant $c_k$ such that a random $d$-dimensional 0/1-polytope with at most $2^{c_kd}$ vertices is $k$-neighborly with high probability. Result (b) shows that it is not sufficient to consider vertex expansion to prove the conjecture of Mihail and Vazirani. On the other hand it seems that the technics used to prove (b) can not be used to prove an upper bound on the edge expansion. Results (a) and (b) show typical properties of random 0/1-polytopes. In view of these results it is not extraordinary that certain polytopes from combinatorial optimization have dense graphs, since these 0/1-polytopes have sub-exponentially many vertices (in the dimension $d$). Well known examples are the traveling salesman polytopes and the cut polytopes. In the last chapter, we introduce revlex-initial 0/1-polytopes, a deterministic class of special knapsack polytopes with very few edges and facets. They are used to build a class that has a 0/-polytope with sparse graph and few facets for each dimension $d$ and reasonable number of vertices $n$. This is the first result towards a "lower bound theorem" for 0/1-polytopes (1). Despite the sparse graph all these polytopes satisfy the conjecture of Mihail and Vazirani (2). At the end, we introduce extended revlex-initial 0/1-polytopes which are still knapsack polytopes and might be interesting to investigate regarding the conjecture of Mihail and Vazirani