Open Access Te Herenga Waka-Victoria University of Wellington
Browse

Randomness in classes of matroids

Download (893.64 kB)
Version 2 2023-09-22, 01:43
Version 1 2021-11-23, 10:32
thesis
posted on 2023-09-22, 01:43 authored by Critchlow, William

This thesis is inspired by the observation that we have no good random model for matroids. That stands in contrast to graphs, which admit a number of elegant random models. As a result we have relatively little understanding of the properties of a "typical" matroid. Acknowledging the difficulty of the general case, we attempt to gain a grasp on randomness in some chosen classes of matroids.  Firstly, we consider sparse paving matroids, which are conjectured to dominate the class of matroids (that is to say, asymptotically almost all matroids would be sparse paving). If this conjecture were true, then many results on properties of the random sparse paving matroid would also hold for the random matroid. Sparse paving matroids have limited richness of structure, making counting arguments in particular more feasible than for general matroids. This enables us to prove a number of asymptotic results, particularly with regards to minors.  Secondly, we look at Graham-Sloane matroids, a special subset of sparse paving matroids with even more limited structure - in fact Graham-Sloane matroids on a labelled groundset can be randomly generated by a process as simple as independently including certain bases with probability 0.5. Notably, counting Graham-Sloane matroids has provided the best known lower bound on the total number of matroids, to log-log level. Despite the vast size of the class we are able to prove severe restrictions on what minors of Graham-Sloane matroids can look like.  Finally we consider transversal matroids, which arise naturally in the context of other mathematical objects - in particular partial transversals of set systems and partial matchings in bipartite graphs. Although transversal matroids are not in one-to-one correspondence with bipartite graphs, we shall link the two closely enough to gain some useful results through exploiting the properties of random bipartite graphs. Returning to the theme of matroid minors, we prove that the class of transversal matroids of given rank is defined by finitely many excluded series-minors. Lastly we consider some other topics, including the axiomatisability of transversal matroids and related classes.

History

Copyright Date

2018-01-01

Date of Award

2018-01-01

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

CC BY 4.0

Degree Discipline

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level

Doctoral

Degree Name

Doctor of Philosophy

Victoria University of Wellington Unit

School of Mathematics and Statistics

ANZSRC Type Of Activity code

1 PURE BASIC RESEARCH

Victoria University of Wellington Item Type

Awarded Doctoral Thesis

Language

en_NZ

Victoria University of Wellington School

Centre for Mathematics and Science Education

Advisors

Mayhew, Dillon