Linkages in Large Graphs and Matroid Union

Abstract

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.