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_4^2$, $U_5^2$, $U_5^3$, $C_5$, $C_5^{\ast }$, $U_4^2\oplus U_2^1$, $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