Contributions to the Problems of Recognizing and Coloring Gammoids

Albrecht, Immanuel

This work provides a thorough introduction to the field of gammoids and presents new results that are considered helpful for solving the problems of recognizing and coloring gammoids. Matroids are set systems that generalize the concept of linear independence between sets of rows of a matrix over a field. Gammoids are those matroids that may be represented by directed graphs where the corresponding independence is modeled as the existence of certain families of pair-wise vertex disjoint paths. The seminal papers in gammoid theory have been written by J.H. Mason [2], A.W. Ingleton and M.J. Piff [1]. Natural applications of gammoids can be found within the realms of connectivity of both directed and undirected graphs. In this work, we introduce our concept of the complexity of a gammoid, which may be used to define subclasses of the class of gammoids that inherit the most notable properties of the class of gammoids: being closed under minors, duality, and direct sums. Furthermore, we provide a comprehensive method for deciding whether a given matroid is a gammoid. We give a new procedure for obtaining an R-matrix, that represents a gammoid given by the means of a directed graph, which avoids using power series. We present the first purely combinatorial way of obtaining orientations of gammoids. We prove that every lattice path matroid is 3-colorable. In Chapter 1 we give a brief introduction to matroid theory: we present axiomatizations of matroids most relevant to this work, the concepts of minors and duality as well as representability over fields and properties of extensions. The same chapter also contains a brief introduction to the theory of transversals, including the Theorems of Hall, Rado, Ore, and Perfect, and an introduction to transversal matroids. Also, we provide a short introduction to directed graphs, we introduce the concept of a routing in a directed graph and we close the chapter with Menger’s Theorem and its consequences. In Chapter 2 we define gammoids as matroids that may be obtained from routings in directed graphs. We explore the properties of their directed graph representations and along that we define our notion of a duality respecting representation which correlates the duality-like notion of opposite directed graphs with the notion of duality with respect to gammoids. Furthermore, we introduce our three complexity measures for gammoids that yield subclasses of gammoids which are closed under minors and duality. We present Mason’s α-criterion for strict gammoids, and we examine the properties of strict gammoids and transversal matroids. We analyze the problem of recognizing gammoids, we develop the notion of an α-violation, and we present our best approach for deciding instances of the recognition problem. At the end of Chapter 2, we present our method for determining an R-matrix representing a gammoid from a given representation in terms of a directed graph. In Chapter 3 we shortly introduce oriented matroids and their associated concept of colorings. We show that all orientations of lattice path matroids have 3-colorings. Then we introduce our concept of a heavy arc orientation of a gammoid that yields a purely combinatorial way to obtain representable orientations of gammoids. In Chapter 4 we summarize our new results and give an overview of new and old open problems. [1] A.W. Ingleton and M.J. Piff. Gammoids and transversal matroids. Journal of Combinatorial Theory, Series B, 15(1):51–68, 1973. [2] J.H. Mason. On a class of matroids arising from paths in graphs. Proceedings of the London Mathematical Society, 3(1):55–74, 1972.

Diese Arbeit gibt eine gründliche Einführung in das Gebiet der Gammoide, und legt neue Ergebnisse dar, die für die Probleme des Erkennens und des Färbens von Gammoiden dienlich sind. Matroide sind Mengensysteme, welche den Begriff der linearen Unabhängigkeit zwischen Mengen von Zeilen einer Matrix über einem Körper verallgemeinern. Gammoide sind jene Matroide, welche so durch gerichtete Graphen dargestellt werden können, dass ihre zugehörige Unabhängigkeit durch die Existenz gewisser Familien von paarweise knotendisjunkten Pfaden beschreibbar ist. Die grundlegenden Arbeiten zur Theorie der Gammoide wurden von J.H. Mason [2], A.W. Ingleton und M.J. Piff [1] verfasst. Natürliche Anwendung finden Gammoide im Bereich des Zusammenhangs sowohl von gerichteten als auch von ungerichteten Graphen. In dieser Arbeit führen wir unseren Begriff der Komplexität eines Gammoids ein, welcher verwendet werden kann, um Unterklassen der Klasse der Gammoide zu definieren. Diese Unterklassen erben die bedeutendsten Eigenschaften der Klasse der Gammoide, nämlich die Abgeschlossenheit unter Minoren, unter Dualität sowie unter direkten Summen. Des Weiteren stellen wir eine umfassende Methode bereit, mit der entschieden werden kann, ob ein gegebenes Matroid ein Gammoid ist. Wir geben eine neue Vorgehensweise an, die eine R-Matrix-Darstellung eines Gammoids, welches mittels eines gerichteten Graphen gegeben ist, findet, ohne auf Potenzreihen zurückzugreifen. Wir stellen das erste rein kombinatorische Verfahren vor, dass Orientierungen eines Gammoids liefert. Wir zeigen, dass alle Lattice-Path-Matroide 3-färbbar sind. Im ersten Kapitel geben wir eine kurze Einführung in die Matroidtheorie: Wir stellen die Axiomatisierungen von Matroiden, welche am besten zu dieser Arbeit passen, den Minorenbegriff, die Dualität sowie die Darstellbarkeit über Körpern und Eigenschaften von Erweiterungen vor. Das Kapitel enthält außerdem eine Einführung in die Transversaltheorie, welche die Sätze von Hall, Rado, Ore und Perfect sowie eine Einführung der Transversalmatroide umfasst. Außerdem stellen wir gerichtete Graphen kurz vor, erläutern den Begriff des Routings in gerichteten Graphen und beenden das Kapitel mit dem Satz von Menger sowie Schlussfolgerungen aus diesem. Im zweiten Kapitel definieren wir Gammoide als Matroide, die durch Routings in gerichteten Graphen beschrieben werden können. Wir untersuchen die Eigenschaften ihrer Darstellungen mit gerichteten Graphen und definieren dabei unseren Begriff einer dualitätsachtenden Darstellung, welche den dualitätsnahen Begriff gegenläufig gerichteter Graphen und den Dualitätsbegriff von Gammoiden in Wechselbeziehung stellt. Weiterhin stellen wir drei Komplexitätsmaße für Gammoide vor, welche Unterklassen von Gammoiden liefern, die unter Minoren und Dualität abgeschlossen sind. Wir stellen Mason’s α-Kriterium für strikte Gammoide vor, und wir untersuchen die Eigenschaften von strikten Gammoiden und von Transversalmatroiden. Wir analysieren das Problem des Erkennens von Gammoiden, wir entwickeln den Begriff der α-Verletzung und wir präsentieren unseren besten Ansatz zum Entscheiden, ob ein Matroid ein Gammoid ist. Zum Schluß des zweiten Kapitels stellen wir unsere Methode vor, eine RMatrix-Darstellung eines Gammoids aus einer Darstellung vermöge gerichteter Graphen zu erhalten. Im dritten Kapitel geben wir eine kurze Einführung in orientierte Matroide und den damit verbundenen Begriff der Färbung. Wir zeigen, dass alle Orientierungen von Lattice-Path-Matroiden eine 3-Färbung besitzen. Danach stellen wir unseren Begriff der Heavy-Arc-Orientierung eines Gammoids vor, welcher eine rein kombinatorische Vorgehensweise, eine repräsentierbare Orientierung eines Gammoids zu finden, liefert. Im vierten Kapitel resümieren wir unsere neuen Resultate und geben einen Überblick über neue und alte offene Fragestellungen.[1] A.W. Ingleton and M.J. Piff. Gammoids and transversal matroids. Journal of Combinatorial Theory, Series B, 15(1):51–68, 1973. [2] J.H. Mason. On a class of matroids arising from paths in graphs. Proceedings of the London Mathematical Society, 3(1):55–74, 1972

Vorschau

Zitieren

Zitierform:

Albrecht, Immanuel: Contributions to the Problems of Recognizing and Coloring Gammoids. 2018. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:

Export

powered by MyCoRe