A Dual Independence Complex
| dc.contributor.advisor | Ziegler, Günter M. | en |
| dc.contributor.author | Waßmer, Arnold Johannes | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2005-09-02 | |
| dc.date.accessioned | 2015-11-20T16:32:12Z | |
| dc.date.available | 2005-09-23T12:00:00Z | |
| dc.date.issued | 2005-09-23 | |
| dc.date.submitted | 2005-09-23 | |
| dc.description.abstract | In der vorliegenden Arbeit verbinden wir das Konzept der Dualität mit dem Unabhängigkeitskomplex von Graphen. Der Unabhängigkeitskomplex eines Graphen ist der Simplizialkomplex seiner unabhängigen (stabilen) Mengen. Wir beweisen, dass für Pfade und Kreise dieser Unabhängigkeitskomplex dualisiert werden kann. Dieser so erhaltene duale Unabhängigkeitskomplex weist überraschende Strukturen auf: Er enthält die gleiche topologische Information wie der nicht-duale Komplex; sein Homöomorphietyp ist durch die Dualisierung jedoch wesentlich schöner geworden. Beispielsweise ist der Unabhängigkeitskomplex eines Kreises entweder homotopieäquivalent zu einer Sphäre oder zur Verheftung zweier Sphären. Im allgemeinen ist dies ein nicht-reiner Simplizialkomplex. Durch die Dualisierung erhält man einen Komplex des gleichen Homotopietyps. Er ist aber sogar homöomorph zur entsprechenden Sphäre beziehungsweise zu einer so genannten Sphäre mit einer dritten Hemisphäre. Um die technischen Grundlagen dieses Beweises zu schaffen, werden hauptsächlich Bäume studiert. Zunächst wird für jeden Baum T die Halbordnung DIP(T) definiert. Ihre Elemente sind die unabhängigen Mengen I, deren Link im Unabhängigkeitskomplex IC(T) nicht kontrahierbar ist. Die Halbordnung auf DIP(T) ist gegeben durch umgekehrte Inklusion der unahängigen Mengen. Für Pfade P zeigen wir, dass diese Halbordnung DIP(P) graduiert ist, die Diamanteigenschaft hat und eine rekursive Koatomordnung zulässt. Diese drei Eigenschaften haben zur Folge, dass es einen regulären Zellkomplex DIC(P) gibt, dessen Seitenhalbordnung DIP(P) ist. Diesen Komplex nennen wir den dualen Unabhängigkeitskomplex. Für alle Pfade ist er ein schälbarer Ball. Die Dimension dieses Balles hängt von der Länge des Pfades ab. Analog weisen wir für jeden Kreis C nach, dass es ebenfalls einen regulären Zellkomplex DIC(C) mit Seitenhalbordnung DIP(C) gibt. Wir zeigen, dass dieser duale Unabhängigkeitskomplex DIC(C) schälbar ist und den bereits erwähnten Homöomorphietyp hat. Schliesslich zeigen wir, dass die Symmetriegruppe des Komplexes DIC(C) die Diedergruppe ist. Für Bäume können wir einige ähnliche Resultate zeigen. Wir können ebenfalls nachweisen, dass die die Halbordnung DIP(T) von Bäumen T graduiert ist und die Diamanteigenschaft hat. Überraschenderweise sind die Beweise sehr ähnlich wie im Sonderfall von Pfaden. Das wesentliche Beweiswerkzeug in beiden Fällen ist die Klassifizierung der Knoten von Bäumen in sechs Typen: Wölfe, Hunde, lebendige und tote Schafe, Fliegenpilze und Champignons. Wir vermuten, dass für alle Bäume T die Halbordnung DIP(T) die Seitenhalbordnung eines regulären Zellkomplexes ist. Mit anderen Worten: Der Unabhängigkeitskomplex von Bäumen kann vermutlich ebenfalls dualisiert werden. Wie ein möglicher Beweis dieser Vermutung aussehen könnte, wird am Ende der Arbeit diskutiert. | de |
| dc.description.abstract | In the present work we apply the concept of duality to the simplicial complex of independent (stable) sets of graphs, the so called independence complex. We prove that this complex can be dualized for the case of paths and cycles. The result is a dual independence complex, which is a regular cell complex with surprising structures. Although it contains the same topological information as the non-dual complex its homeomorphism type is "nicer". The independence complex of a cycle, for example, is either homotopy equivalent to a sphere or to a wedge of two spheres. In general, it is a non-pure complex. The corresponding dual independence complex has the same homotopy type. Moreover, it is homeomorphic to a sphere or to a sphere with a third hemisphere. In order to provide the basic tools for this theory we start by studying trees. First we define for every tree T its dual independence poset DIP(T). Its elements are the independent sets I whose links in the indepencence complex IC(T) are not contractible. The partial order on DIP(T) is given by reverse inclusion. We prove that for every path P this poset DIP(P) is graded, has the diamond property and has a recursive coatom ordering. These properties imply that there is a regular cell complex DIC(P) with face poset DIP(P). We show that this complex is a shellable ball, its dimension is determined by the length of the path P. Similarly, we prove for each cycle C that there is a regular cell complex DIC(C) with face poset DIP(C). We show that this dual independence complex DIC(C) is shellable and has the homeomorphism type described above. Finally, we show that the symmetry group of the complex DIC(C) is a dihedral group. We prove similar results for trees. We show for all trees T that the poset DIP(T) is graded and has the diamond property. These proofs for trees are very similar to the special cases of paths. At the heart of all these proofs is a classification of the nodes of trees into six different types: wolves, dogs, living and dead sheep, toadstools and mushrooms. We conjecture that for each tree T the poset DIP(T) is the poset of a regular cell complex. In other words, we conjecture that the independence complexes of all trees can be dualized. We conclude with a discussion of this conjecture. | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-11070 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/1495 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-1198 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Dualität | de |
| dc.subject.other | Graphen | de |
| dc.subject.other | Stabile Mengen | de |
| dc.subject.other | Unabhängige Mengen | de |
| dc.subject.other | Unabhängigkeitskomplex | de |
| dc.subject.other | Duality | en |
| dc.subject.other | Graphs | en |
| dc.subject.other | Independence complex | en |
| dc.subject.other | Independent sets | en |
| dc.subject.other | Stable sets | en |
| dc.title | A Dual Independence Complex | en |
| dc.title.translated | Ein dualer Unabhängigkeitskomplex | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 1107 | |
| tub.identifier.opus4 | 1105 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1