On Matroid and Polymatroid Connectivity

Matroids were introduced in 1935 by Hassler Whitney to provide a way to abstractly capture the dependence properties common to graphs and matrices. One important class of matroids arises by taking as objects some finite collection of one-dimensional subspaces of a vector space. If, instead, one takes as objects some finite collection of subspaces of dimensions at most k in a vector space, one gets an example of a k-polymatroid. Connectivity is a pivotal topic of study in the endeavor to understand the structure of matroids and polymatroids. In this dissertation, we study the notion of connectivity from several angles. It is a well-known result of Tutte that, for every element x of a connected matroid M, at least one of the deletion and contraction of x from M is connected. Our first result shows that, in a connected k-polymatroid, only two such elements are guaranteed. We show that this bound is sharp and characterize those 2-polymatroids that achieve this minimum. It is well known that, for any integer n greater than one, there is a number r such that every 2-connected simple graph with at least r edges has a minor isomorphic to an n-edge cycle or K2,n. This result was extended to matroids by Lovász, Schrijver, and Seymour who proved that every sufficiently large connected matroid has an n-element circuit or an n-element cocircuit as a minor. As our second result, we generalize these theorems by providing an analogous result for connected 2-polymatroids. Significant progress on the corresponding problem for k-polymatroids is also described. Finally, we look at tangles, a tool that has been used extensively in recent results in matroid structure theory. We prove that a matroid with at least two elements is a tangle matroid if and only if it cannot be covered by three hyperplanes. Some consequences of this theorem are also noted. In particular, no binary matroid of rank at least two is a tangle matroid