Aspects of Matroid Connectivity

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Mathematics
Degree name
Doctor of Philosophy
Publisher
University of Canterbury. School of Mathematics and Statistics
Journal Title
Journal ISSN
Volume Title
Language
Date
2014
Authors
Brettell, Nicholas John
Abstract

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.

Description
Citation
Keywords
matroid theory, connectivity, chain theorem, splitter theorem, tree decomposition, k-tree, polynomial-time algorithm
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
Copyright Nicholas John Brettell