Contributions to the Problems of Recognizing and Coloring Gammoids
Immanuel Albrecht · arXiv (Cornell University) · 2018
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.