Boolean Representations of Matroids and Lattices

2011/08/06 by Zur Izhakian, Izhakian, Zur, John Rhodes +1 · 4 citations
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Advanced Graph Theory Research #Advanced Combinatorial Mathematics

paper · pdf · doi:10.48550/arxiv.1108.1473

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.

Cited by

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

Related

• Matroids, hereditary collections and simplicial complexes having boolean representations
• New Representations of Matroids and Generalizations
• Combinatorial representations
• On the Dowling and Rhodes lattices and wreath products
• On the lattice of flats of a boolean representable simplicial complex