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.
| Identifer | oai:union.ndltd.org:canterbury.ac.nz/oai:ir.canterbury.ac.nz:10092/9215 |
| Date | January 2014 |
| Creators | Brettell, Nicholas John |
| Publisher | University of Canterbury. School of Mathematics and Statistics |
| Source Sets | University of Canterbury |
| Language | English |
| Detected Language | English |
| Type | Electronic thesis or dissertation, Text |
| Rights | Copyright Nicholas John Brettell, http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml |
| Relation | NZCU |
Page generated in 0.0025 seconds