K—Regular Matroids

Abstract

The class of matroids representable over all fields is the class of regular matroids. The class of matroids representable over all fields except perhaps GF(2) is the class of near-regular matroids. Let k be a non-negative integer. This thesis considers the class of k-regular matroids, a generalization of the last two classes. Indeed, the classes of regular and near-regular matroids coincide with the classes of 0-regular and 1-regular matroids, respectively. This thesis extends many results for regular and near-regular matroids. In particular, for all k, the class of k-regular matroids is precisely the class of matroids representable over a particular partial field. Every 3-connected member of the classes of either regular or near-regular matroids has a unique representability property. This thesis extends this property to the 3-connected members of the class of k-regular matroids for all k. A matroid is ω-regular if it is k-regular for some k. It is shown that, for all k ≥ 0, every 3-connected k-regular matroid is uniquely representable over the partial field canonically associated with the class of ω-regular matroids. To prove this result, the excluded-minor characterization of the class of k-regular matroids within the class of ω-regular matroids is first proved. It turns out that, for all k, there are a finite number of ω-regular excluded minors for the class of k-regular matroids. The proofs of the last two results on k-regular matroids are closely related. The result referred to next is quite different in this regard. The thesis determines, for all r and all k, the maximum number of points that a simple rank-r k-regular matroid can have and identifies all such matroids having this number. This last result generalizes the corresponding results for regular and near-regular matroids. Some of the main results for k-regular matroids are obtained via a matroid operation that is a generalization of the operation of ∆ - Y exchange. This operation is called segment-cosegment exchange and, like the operation of ∆ - Y exchange, has a dual operation. This thesis defines the generalized operation and its dual, and identifies many of their attractive properties. One property in particular, is that, for a partial field P, the set of excluded minors for representability over P is closed under the operations of segment-cosegment exchange and its dual. This result generalizes the corresponding result for ∆ - Y and Y - ∆ exchanges. Moreover, a consequence of it is that, for a prime power q, the number of excluded minors for GF(q)-representability is at least 2q-4.