Combinatorial Theory

In this sequel to "Foundations of matroids - Part 1," we establish several presentations of the foundation of a matroid in terms of small building blocks. For example, we show that the foundation of a matroid \(M\) is the colimit of the foundations of all embedded minors of \(M\) isomorphic to one of the matroids \(U^2_4\), \(U^2_5\), \(U^3_5\), \(C_5\), \(C_5^\ast\), \(U^2_4\oplus U^1_2\), \(F_7\), \(F_7^\ast\), and we show that this list is minimal. We establish similar minimal lists of building blocks for the classes of 2-connected and 3-connected matroids. We also establish a presentation for the foundation of a matroid in terms of its lattice of flats. Each of these presentations provides a useful method to compute the foundation of certain matroids, as we illustrate with a number of concrete examples. Combining these techniques with other results in the literature, we are able to compute the foundations of several interesting classes of matroids, including whirls, rank-2 uniform matroids, and projective geometries. In an appendix, we catalogue various `small' pastures which occur as foundations of matroids, most of which were found with the assistance of a computer, and we discuss some of their interesting properties.

Mathematics Subject Classifications: 05B35, 12K99

Keywords: Matroid representation, cross ratio, inner Tutte group, foundations