Skip to main content

On excluded minors and biased graph representations of frame matroids

Resource type
Thesis type
(Thesis) Ph.D.
Date created
A biased graph is a graph in which every cycle has been given a bias, either balanced or unbalanced. Biased graphs provide representations for an important class of matroids, the frame matroids. As with graphs, we may take minors of biased graphs and of matroids, and a family of biased graphs or matroids is minor-closed if it contains every minor of every member of the family. For any such class, we may ask for the set of those objects that are minimal with respect to minors subject to not belonging to the class - i.e., we may ask for the set of excluded minors for the class. A frame matroid need not be uniquely represented by a biased graph. This creates complications for the study of excluded minors. Hence this thesis has two main intertwining lines of investigation: (1) excluded minors for classes of frame matroids, and (2) biased graph representations of frame matroids. Trying to determine the biased graphs representing a given frame matroid leads to the necessity of determining the biased graphs representing a given graphic matroid. We do this in Chapter 3. Determining all possible biased graph representations of non-graphic frame matroids is more difficult. In Chapter 5 we determine all biased graphs representa- tions of frame matroids having a biased graph representation of a certain form, subject to an additional connectivity condition. Perhaps the canonical examples of biased graphs are group-labelled graphs. Not all biased graphs are group-labellable. In Chapter 2 we give two characterisations of those biased graphs that are group labellable, one topological in nature and the other in terms of the existence of a sequence of closed walks in the graph. In contrast to graphs, which are well-quasi-ordered by the minor relation, this characterisation enables us to construct infinite antichains of biased graphs, even with each member on a fixed number of vertices. These constructions are then used to exhibit infinite antichains of frame matroids, each of whose members are of a fixed rank. In Chapter 4, we begin an investigation of excluded minors for the class of frame ma- troids by seeking to determine those excluded minors that are not 3-connected. We come close, determining a set E of 18 particular excluded minors and drastically narrowing the search for any remaining such excluded minors.
Copyright statement
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: DeVos, Matt
Member of collection
Download file Size
etd8841_DFunk.pdf 1.93 MB

Views & downloads - as of June 2023

Views: 10
Downloads: 1