Mathematics Department Colloquium: Boolean representations of simplicial complexes: beyond matroids

Colloquium | August 31 | 4:10-5 p.m. | 60 Evans Hall

 John Rhodes, UC Berkeley

 Department of Mathematics

We present a "crash course" on representing finite simplicial complexes by rectangular matrices with coefficients 0 or 1 (Boolean matrices). Our "course" may be of interest to combinatorialists, topologists, and discrete geometers and is intended to be accessible to students, including advanced undergraduates.

Our main theme is a new idea: some of the columns of a Boolean matrix are "linearly independent" (stemming from Tropical Algebra, which will clearly be explained). The simplicial complex of all such "linearly independent" columns of a fixed Boolean matrix is termed a Boolean representable simplicial complex (BRSC).

The Boolean representable simplicial complexes include all matroids, but not all simplicial complexes. We will reformulate the concept of BRSC's using finite lattices, closure operators, and Galois connections.

Generalizing the case of matroids, we will then explain why BRSC and matroids all come from (combinatorial) geometry. Intuitively, the BRSC form the largest class of finite simplicial complexes coming from any combinatorial geometry.

Time permitting, we will explain the deep connections between BRSC and Design Theory, using the great theorem of R. M. Wilson of the 1970s on the existence of pairwise balanced designs (PBD) and their relation to subgeometries of BRSC.

 ribet@berkeley.edu