FAQ
© 2015 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-70343
URL: http://ediss.sub.uni-hamburg.de/volltexte/2014/7034/


Connected Tree-width and Infinite Gammoids

Zusammenhängende Baumweite und Unendliche Gammoide

Müller, Malte

pdf-Format:
 Dokument 1.pdf (764 KB) 


Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Diestel, Reinhard (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 15.10.2014
Erstellungsjahr: 2014
Publikationsdatum: 05.11.2014
Kurzfassung auf Englisch: 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.
Kurzfassung auf Deutsch: 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.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende