Jul 24, 2015
Friday
|
11:00 AM - 11:45 AM
|
|
A Matroid Generalization of Sperner's Lemma
Gabriel Andrade (University of Massachusetts Amherst), Andres Rodriguez Rey (University of California, San Diego), Alberto Ruiz Sandoval (University of Puerto Rico)
|
- Location
- MSRI: Baker Board Room
- Video
-
- Abstract
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.
- Supplements
-
--
|
|