Randomness in classes of matroids

Abstract

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.