Let $G=(V,E)$ be a graph on $n$ vertices. A separator is a partition of the vertices of the graph into three sets $(A,B,C)$ where $A$ and $B$ are ``large" and there is no edge between a vertex in $A$ and a vertex in $B$. The size of the separator is $|C|$. Lipton and Tarjan showed that all the graphs of three dimensional polytopes have separators of size $O(\sqrt{n})$. In higher dimensions no such result is possible, as there are polytopes that have a complete graph as their graph. The graphs of simple $d$-polytopes are regular with degree $d$. Kalai had conjectured, that the graphs of simple $d$-polytopes would have separators of size $O(n^{\frac{d-2}{d-1}})$. In this work we disprove the conjecture and show that there are simple polytopes whose minimal separators are of size $\Omega(n/\log n)$. We also verify a claim by Thurston, who claimed the existence of dual graphs of triangulations of $S^3$ with this property.
Sei $G=(V,E)$ ein Graph mit $n$ Ecken. Ein Separator ist eine Partition der Ecken des Graphs in drei Mengen $(A,B,C)$, sodass $A$ und $B$ ``gro\ss`` sind und sich keine Kante zwischen einer Ecke in $A$ und einer Ecke in $B$ befindet. Die Gr\"o{\ss}e des Separators ist $|C|$. Lipton und Tarjan haben gezeigt, dass alle Graphen von dreidimensionalen Polytopen Separatoren der Gr\"o{\ss}e $O(\sqrt{n})$ haben. In h\"oheren Dimensionen ist ein solches Resultat nicht m\"oglich, da es dann Polytope gibt, deren Graph vollst\"andig ist. Die Graphen von einfachen Polytopen sind regul\"ar vom Grad $d$. Kalai stellte die Vermutung auf, dass die Graphen von einfachen $d$-dimensionalen Polytopen Separatoren der Gr\"o{\ss}e $O(n^{\frac{d-2}{d-1}})$ h\"atten. In dieser Arbeit widerlegen wir diese Vermutung und zeigen, dass es einfache Polytope gibt, deren minimale Separatoren die Gr\"o{\ss}e $\Omega(n/\log n)$ haben. Wir belegen au{\ss}erdem eine Behauptung von Thurston, wonach Graphen mit dieser Eigenschaft existieren, die die dualen Graphen von Triangulierungen von $S^3$ sind.
