dc.contributor.author
Loiskekoski, Lauri
dc.date.accessioned
2018-06-08T00:23:29Z
dc.date.available
2018-03-28T12:51:46.231Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/11875
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-16073
dc.description.abstract
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.
de
dc.description.abstract
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.
de
dc.format.extent
vi, 33 Seiten
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
simple polytope
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik::516 Geometrie
dc.title
Separators of simple polytopes
dc.contributor.contact
loiskekoski@zedat.fu-berlin.de
dc.contributor.firstReferee
Prof. Dr. Günter M. Ziegler
dc.contributor.furtherReferee
Prof. Dr. Volker Kaibel
dc.date.accepted
2017-12-21
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000106673-9
dc.title.translated
Separatoren der einfachen Polytopen
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000106673
refubium.mycore.derivateId
FUDISS_derivate_000000023423
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access