1 |
Aspects of Matroid ConnectivityBrettell, Nicholas John January 2014 (has links)
Connectivity is a fundamental tool for matroid theorists, which has become increasingly important in the eventual solution of many problems in matroid theory. Loosely speaking, connectivity can be used to help describe a matroid's structure. In this thesis, we prove a series of results that further the knowledge and understanding in the field of matroid connectivity. These results fall into two parts.
First, we focus on 3-connected matroids. A chain theorem is a result that proves the existence of an element, or elements, whose deletion or contraction preserves a predetermined connectivity property. We prove a series of chain theorems for 3-connected matroids where, after fixing a basis B, the elements in B are only eligible for contraction, while the elements not in B are only eligible for deletion. Moreover, we prove a splitter theorem, where a 3-connected minor is also preserved, resolving a conjecture posed by Whittle and Williams in 2013.
Second, we consider k-connected matroids, where k >= 3. A certain tree, known as a k-tree, can be used to describe the structure of a k-connected matroid. We present an algorithm for constructing a k-tree for a k-connected matroid M. Provided that the rank of a subset of E(M) can be found in unit time, the algorithm runs in time polynomial in |E(M)|. This generalises Oxley and Semple's (2013) polynomial-time algorithm for constructing a 3-tree for a 3-connected matroid.
|
Page generated in 0.068 seconds