New representations of matroids and generalizations

Abstract

We extend the notion of matroid representations by matrices over fields by considering new representations of matroids by matrices over finite semirings, more precisely over the boolean and the superboolean semirings. This idea of representations is naturally generalized to include hereditary collections (also known as abstract simplicial complexes). We show that a matroid that can be directly decomposed as matroids, each of which is representable over a field, has a boolean representation, and more generally that any arbitrary hereditary collection is superboolean-representable.