Boolean Representations of Matroids and Lattices

Abstract

We introduce a new representation concept for lattices by boolean matrices, and utilize it to prove that any matroid is boolean representable. We show that such a representation can be easily extracted from a representation of the associated lattice of flats of the matroid, leading also to a tighter bound on the representation's size. Consequently, we obtain a linkage of boolean representations with geometry in a very natural way.

16 pages

References in corpus (3)

• Tropical Arithmetic and Tropical Matrix Algebra
• The Tropical Rank of a Tropical Matrix
• C-independence and c-rank of posets and lattices

Cited by in corpus (4)

• C-independence and c-rank of posets and lattices
• Commutative $\nu$-algebra and supertropical algebraic geometry
• Matroids, hereditary collections and simplicial complexes having boolean representations
• Superboolean rank and the size of the largest triangular submatrix of a random matrix