Algorithmic applications of connectivity and related topics in matroid theory
Arvind Rajan · 1987
This dissertation is the product of research on various aspects of matroid connectivity and decomposition. The theory of Partial Matroid Representations recently developed by Truemper is used to derive a number of new and known results in this area. The dissertation may be naturally subdivided into four parts. First, a conceptually simple and efficient algorithm is described to compute a connectivity based decomposition for a given matroid. It treats 1-, 2- and 3-separations in a unified manner and its overall bound is the best achieved so far. The associated bounds are described for the case when the matroid is binary. The second part examines chains in 4-connected matroids and graphs. It is shown that various generalizations of known chain theorems from 3-connected matroids to 4-connected matroids are false even for graphs. A methodology for obtaining chain results is developed based on Truemper's theory of binders, and is used to derive a restricted chain theorem for vertex 4-connected graphs. The third part contains short proofs of two known matroid decomposition results. The main result is a recent theorem of Truemper and Tseng for the class of matroids with the max-flow min-cut property. The theorem says essentially that every matroid in this class is either isomorphic to the Fano matroid or is decomposable into a 3-sum in a well-defined way. The second result describes the structure of regular matroids, and is an important ingredient in Seymour's decomposition theorem for this class. In the last part, the matroid sum operation is studied from the viewpoint of partial representations. A new interpretation for the sum operation is derived, and used to give a short proof of a theorem of Cunningham characterizing those binary matroids that do not have a sum decomposition. A proof is given for a result conjectured by Cunningham and recently proved by Dawson about the uniqueness of the sum decomposition for binary matroids.