Volltextdatei(en) vorhanden
Titel: Connected Tree-width and Infinite Gammoids
Sonstige Titel: Zusammenhängende Baumweite und Unendliche Gammoide
Sprache: Englisch
Autor*in: Müller, Malte
Erscheinungsdatum: 2014
Tag der mündlichen Prüfung: 2014-10-15
Zusammenfassung: 
The connected tree-width is an upper bound for the tree-width of a graph, and the cycles (as graphs), having a tree-width of 2, show that the tree-width and the connected tree-width of a graph can be arbitrarily far away from each other.
It is proved that for any graph, a large geodesic cycle is the only reason for the connected tree-width to be much larger than the tree-width. This is used to show that a qualitative version of a "connected tree-width duality theorem" holds.

The second part concerns gammoids, a class of matroids investigated in the late 1960's. Ingleton and Piff gave a construction that transforms a presentation of a finite strict gammoid, a dimaze, to a transversal matroid presentation of its dual, a bipartite graph. This is used in the proof that the class of finite gammoids is closed under minors and under duality. In 2010 Bruhn, Diestel, Kriesell, Pendavingh and Wollan found a notion of infinite matroids that allows for duality. This suggests the question of extending gammoids to infinite ground sets by a verbatim transfer of linkability.
Contrary to the finite case, not every infinite dimaze defines a matroid. One obstruction is a dimaze termed an alternating comb. For such a strict gammoid the construction of Ingleton and Piff (transferred to the infinite case) provides a presentation of the dual and, if the dimaze does not contain an incoming ray, that dual is transversal. The class of gammoids definable by a dimaze without any outgoing comb is minor closed and the class of gammoids definable by a dimaze without any ray is, like that of finite gammoids, closed under minors and under duality.

Die zusammenhängende Baumweite eines Graphen ist eine obere Schranke für seine Baumweite und bei einem Kreis können diese beiden Parameter beliebig weit voneinander entfernt sein. Es wird bewiesen, dass einen langen geodätischen Kreis zu enthalten der einzige Grund für einen großen Abstand dieser Parameter ist. Dies wird benutzt um eine qualitative Version eines "Dualitätssatzes der zusammenhängenden Baumweite" zu beweisen.

Im zweiten Teil beschäftigen wir uns mit den, in den 1960er Jahren entwickelten, Gammoiden. Eine Konstruktion von Ingleton und Piff überführt eine Präsentation eines endlichen strikten Gammoids, ein Dimaze, in eine transversal Matroid-Präsentation des Duals, einen bipartiten Graphen. Sie wurde benutzt um zu beweisen, dass die endlichen Gammoide unter Minorbildung und Dualität abgeschlossen sind. Im Jahr 2010 fanden Bruhn, Diestel, Kriesell, Pendavingh und Wollan Axiome für unendliche Matroide, die Dualität erlauben. Eine natürliche Frage ist, ob sich Gammoide, durch wörtliche Übertragung von Verbindbarkeit, auf unendliche Grundmengen erweitern lassen.
Im Gegensatz zum endlichen Fall definiert nicht jedes unenliche Dimaze ein Matroid. Enthält es allerdings kein Dimaze namens alternating comb, so wird ein Matroid definiert und die Konstuktion von Ingleton und Piff (auf den unendlichen Fall übertragen) liefert eine Präsentation vom Dual des definierten strikten Gammoids. Falls das Dimaze keinen incoming comb enthielt, so ist dieses Dual ein transversal Matroid. Die Klasse der Gammoide, die eine Präsentation ohne outgoing comb haben, ist unter Minorbildung abgeschlossen und die Klasse der Gammoide, die durch ein strahlenloses Dimaze definierbar sind, ist, wie die der endlichen Gammoide, unter Minorbildung und Dualität abgeschlossen.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/5649
URN: urn:nbn:de:gbv:18-70343
Dokumenttyp: Dissertation
Betreuer*in: Diestel, Reinhard (Prof. Dr.)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung Prüfsumme GrößeFormat  
Dissertation.pdf90ae2c34578dfbbb6681b82ff874bf36764.1 kBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Diese Publikation steht in elektronischer Form im Internet bereit und kann gelesen werden. Über den freien Zugang hinaus wurden durch die Urheberin / den Urheber keine weiteren Rechte eingeräumt. Nutzungshandlungen (wie zum Beispiel der Download, das Bearbeiten, das Weiterverbreiten) sind daher nur im Rahmen der gesetzlichen Erlaubnisse des Urheberrechtsgesetzes (UrhG) erlaubt. Dies gilt für die Publikation sowie für ihre einzelnen Bestandteile, soweit nichts Anderes ausgewiesen ist.

Info

Seitenansichten

182
Letzte Woche
Letzten Monat
geprüft am 27.03.2024

Download(s)

50
Letzte Woche
Letzten Monat
geprüft am 27.03.2024
Werkzeuge

Google ScholarTM

Prüfe