A Matroid Generalization of Sperner's Lemma

In a 1980 paper, Lov´asz generalized Sperner’s lemma for matroids. He claimed that a triangulation of a d-simplex labeled with elements of a matroid M must contain at least one “basis simplex”. We present a counterexample to Lov´asz’s claim when the matroid contains singleton dependent sets and provide an additional su⇤cient condition that corrects Lov´asz’s result. Furthermore, we show that under some conditions on the matroids, there is an improved lower bound on the number of basis simplices. We present further work to sharpen this lower bound by looking at M’s lattice of flats and by proving that there exists a group action on the simplex labeled by M with Sn.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.