Die Arbeit besteht hauptsächlich aus zwei Teilen: einer Zusammenfassung kombinatorischer und algebraisch-geometrischer Themen (Gitterpolytope, torische (Gorenstein-)Varietäten, und Matroide), und einem Ergebnisteil. Letzerer besteht aus zwei Teilen. Im ersten Teil wird eine konstruktive Klassifikation von Multigraphen, deren graphisches Matroid ein Basispolytop erzeugt, das die Gorenstein-Eigenschaft erfüllt, erarbeitet. Im zweiten Teil wird ein Satz rekursiver Formeln, die die Ehrhartpolynome von symmetrischen Kantenpolytopen, die aus vollständig-biparten Graphen hervorgehen, zueinander in Beziehung stellen, vorgestellt. Außerdem wird Algorithmus, mit dem man solche Formel erzeugen kann, aufgezeigt.:1. Introduction 2. Notation 3. Preliminaries 3.1 Lattice Polytopes 3.2 Toric Varieties 3.3 Matroids 3.4 Gorenstein Toric Varieties 4. Results 4.1 Gorenstein Matroids 4.2 Recursive Formulas of Symmetric Edge Polytopes

Techn. University, Diss., 2007--Darmstadt.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

A spectral graph realization is an embedding of a finite simple graph into Euclidean space that is constructed from the eigenvalues and eigenvectors of the graph's adjacency matrix. It has previously been observed that some polytopes can be reconstructed from their edge-graphs by taking the convex hull of a spectral realization of this edge-graph. These polytopes, which we shall call spectral polytopes, have remarkable rigidity and symmetry properties and are a source for many open questions. In this thesis we aim to further the understanding of this phenomenon by exploring the geometric and combinatorial properties of spectral polytopes on several levels. One of our central questions is whether already weak forms of symmetry can be a sufficient reason for a polytope to be spectral. To answer this, we derive a geometric criterion for the identification of spectral polytopes and apply it to prove that indeed all polytopes of combined vertex- and edge-transitivity are spectral, admit a unique reconstruction from the edge-graph and realize all the symmetries of this edge-graph. We explore the same questions for graph realizations and find that realizations of combined vertex- and edge-transitivity are not necessarily spectral. Instead we show that we require a stronger form of symmetry, called distance-transitivity. Motivated by these findings we take a closer look at the class of edge-transitive polytopes, for which no classification is known. We state a conjecture for a potential classification and provide complete classifications for several sub-classes, such as distance-transitive polytopes and edge-transitive polytopes that are not vertex-transitive. In particular, we show that the latter class contains only polytopes of dimension d <= 3. As a side result we obtain the complete classification of the vertex-transitive zonotopes and a new characterization for root systems.