Volltextdatei(en) vorhanden
Titel: Linkages in Large Graphs and Matroid Union
Sonstige Titel: Wegverbindungen in großen Graphen und die Vereinigung von Matroiden
Sprache: Englisch
Autor*in: Fröhlich, Jan-Oliver
Schlagwörter: beschränkte Baumweite; Zusammenhang; Wegverbundenheit; unendliches Matroid; Matroidvereinigung; unendlicher Satz von Menger; bounded tree-width; connectivity; linkedness; infinite matroid; matroid union; infinite Menger theorem
GND-Schlagwörter: BaumweiteGND
GraphGND
Weg
Dekomposition
MatroidGND
Unendlichkeit
Vereinigung
Zyklenraum
Erscheinungsdatum: 2014
Tag der mündlichen Prüfung: 2014-03-19
Zusammenfassung: 
This cumulative dissertation consists of the three papers, "Linkages in Large Graphs of Bounded Tree-Width" (chapter 1), "Infinite matroid union" (chapter 2), and "On the intersection of infinite matroids" (chapter 3), that all belong to the area of discrete mathematics and involve very large or infinite structures.

The smallest known function f such that every f(k)-connected graph is k-linked is f(k)=10k as shown by Thomas and Wollan in 2005. In "Linkages in Large Graphs of Bounded Tree-Width" we show that for all positive integers k and w there is an integer N such that every (2k+3)-connected graph G of tree-width less than w on at least N vertices is k-linked.

The papers "Infinite matroid union" and "On the intersection of infinite matroids" extend the notion of a union of two finite matroids to infinite matroids and apply the derived union theorem.

In the former paper, we show that the union of two infinite matroids need not be a matroid. We establish a union theorem for a superclass of the finitary matroids (matroids with no infinite cycle), called the nearly finitary matroids and show that for every matroid that is not nearly finitary and satisfies a certain countability condition there is a finitary matroid such that the union of the two is not a matroid. We use the union theorem for finitary matroids to obtain base covering and base packing results for finitary and co-finitary matroids, respectively.

In the latter paper, we show that Nash-Williams' infinite matroid intersection conjecture implies the infinite Menger theorem. We also establish a link between our union theorem and Nash-Williams' conjecture by the use of exchange chains, a technique that we also used in the former paper to show that any union of two matroids satisfies the independence axiom (I3). Finally, we explore the implications of the matroidal framework developed in both papers for cycle matroids of graphs.

Diese kumulative Dissertation besteht aus drei Arbeiten, "Linkages in Large Graphs of Bounded Tree-Width" (Kapitel 1), "Infinite matroid union" (Kapitel 2) und "On the intersection of infinite matroids" (Kapitel 3), die alle zum Gebiet der diskreten Mathematik zu zählen sind und sich mit sehr großen oder unendlichen Strukturen beschäftigen.

Die kleinste bekannte Funktion f, so dass jeder f(k)-zusammenhängende Graph k-verbunden ist, ist f(k)=10k und wurde 2005 von Thomas und Wollan gefunden. In "Linkages in Large Graphs of Bounded Tree-Width" zeigen wir, dass es für alle natürlichen Zahlen k und w eine natürliche Zahl N gibt, so dass jeder (2k+3)-zusammenhängende Graph G der Baumweite kleiner w auf mindestens N Ecken k-verbunden ist.

Die Arbeiten "Infinite matroid union" und "On the intersection of infinite matroids" erweitern den Begriff der Vereinigung zweier endlicher Matroide auf unendliche Matroide und wenden den dafür hergeleiteten Vereinigungssatz an.

In der ersten Matroid-Arbeit zeigen wir, dass die Vereinigung zweier unendlicher Matroide kein Matroid sein muss. Wir beweisen einen Vereinigungssatz für eine Oberklasse der finitären Matroide (solche ohne unendlichen Kreis), die der fast finitären Matroide, und konstruieren für jedes Matriod, das nicht fast finitär ist und einer gewissen Abzählbarkeitsbedingung genügt, ein finitäres Matroid, so dass die Vereinigung der beiden kein Matroid ist. Mit dem Vereinigungssatz für finitäre Matroide zeigen wir einen Basisüberdeckungs-Satz für finitäre und einen Basispackungs-Satz für co-finitäre Matroide.

In der zweiten Matroid-Arbeit leiten wir den unendlichen Satz von Menger aus Nash-Williams' Schnitt-Vermutung für unendliche Matroide her. Wir finden außerdem eine Verbindung zwischen unserem Vereinigungssatz und Nash-Williams' Vermutung durch die Anwendung von Austauschketten, einer Technik, die wir in unserer ersten Matroid-Arbeit eingeführt haben, um nachzuweisen, dass die Vereinigung zweier Matroide stets dem Unabhängigkeitsaxiom (I3) genügt. Schlussendlich untersuchen wir die Folgen der in beiden Arbeiten entwickelten Resultate für Kreismatroide von Graphen.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/5398
URN: urn:nbn:de:gbv:18-67361
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.pdf0f975ccc4ed091fb596cf1a999bd3e174.58 MBAdobe 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

528
Letzte Woche
Letzten Monat
geprüft am 27.03.2024

Download(s)

71
Letzte Woche
Letzten Monat
geprüft am 27.03.2024
Werkzeuge

Google ScholarTM

Prüfe