A MATROID GENERALIZATION FOR SPERNER'S LEMMA
Andres Rodriguez1, Gabriel Andrade2, Alberto Ruiz Sandoval3, Francis Su4.
1Universidad de los Andes, Bogotá, CO, 2University of Massachusetts, Amherst, Amherst, MA, 3University of Puerto Rico, Rio Piedras Campus, San Juan, PR, 4Harvey Mudd College, Claremont, CA.
Previously, Lovász generalized Sperner's lemma for matroids. He claimed that a triangulation of a d-simplex labeled with the elements of a matroid M, while labeling the main vertices with a basis B, must contain at least 1 basis simplex on T, a simplex whose labels form a basis of the matroid. We present a counterexample to Lovász's claim when the matroid contains loops and provide a necessary condition such that Lovász's generalization holds. Under Lovász's construction one can induce a Sperner labeling by fixing the order of the basis B. We prove that any fully labeled simplex on the induced Sperner labeling has to be a basis simplex, giving a new proof of Lovász's claim. Furthermore, we show that for some matroids there is an improved lower bound on the number of basis simplices. Finally, 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 induced Sperner's labelings by Sn.