Linkages in Large Graphs and Matroid Union
Jan-Oliver Fröhlich · 2014
This cumulative dissertation consists of the three papers, Linkages in Large Graphs of Bounded Tree-Width (chapter 1), Infinite matroid (chapter 2), and On the intersection of infinite (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 and On the intersection of infinite 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 (Kapitel 2) und On the intersection of infinite (Kapitel 3), die alle zum Gebiet der diskreten Mathematik zu zahlen sind und sich mit sehr grosen oder unendlichen Strukturen beschaftigen. Die kleinste bekannte Funktion f, so dass jeder f(k)-zusammenhangende 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 fur alle naturlichen Zahlen k und w eine naturliche Zahl N gibt, so dass jeder (2k+3)-zusammenhangende Graph G der Baumweite kleiner w auf mindestens N Ecken k-verbunden ist. Die Arbeiten Infinite matroid und On the intersection of infinite erweitern den Begriff der Vereinigung zweier endlicher Matroide auf unendliche Matroide und wenden den dafur hergeleiteten Vereinigungssatz an. In der ersten Matroid-Arbeit zeigen wir, dass die Vereinigung zweier unendlicher Matroide kein Matroid sein muss. Wir beweisen einen Vereinigungssatz fur eine Oberklasse der finitaren Matroide (solche ohne unendlichen Kreis), die der fast finitaren Matroide, und konstruieren fur jedes Matriod, das nicht fast finitar ist und einer gewissen Abzahlbarkeitsbedingung genugt, ein finitares Matroid, so dass die Vereinigung der beiden kein Matroid ist. Mit dem Vereinigungssatz fur finitare Matroide zeigen wir einen Basisuberdeckungs-Satz fur finitare und einen Basispackungs-Satz fur co-finitare Matroide. In der zweiten Matroid-Arbeit leiten wir den unendlichen Satz von Menger aus Nash-Williams' Schnitt-Vermutung fur unendliche Matroide her. Wir finden auserdem eine Verbindung zwischen unserem Vereinigungssatz und Nash-Williams' Vermutung durch die Anwendung von Austauschketten, einer Technik, die wir in unserer ersten Matroid-Arbeit eingefuhrt haben, um nachzuweisen, dass die Vereinigung zweier Matroide stets dem Unabhangigkeitsaxiom (I3) genugt. Schlussendlich untersuchen wir die Folgen der in beiden Arbeiten entwickelten Resultate fur Kreismatroide von Graphen.