Home /  MsriUp /  Schedules /  A Matroid Generalization of Sperner's Lemma

A Matroid Generalization of Sperner's Lemma

MSRI-UP 2015: Geometric Combinatorics Motivated by the Social Sciences June 13, 2015 - July 26, 2015

July 24, 2015 (11:00 AM PDT - 11:45 AM PDT)
Speaker(s): Gabriel Andrade (University of Massachusetts Amherst), Andres Rodriguez Rey (University of California, San Diego), Alberto Ruiz Sandoval (University of Puerto Rico)
Location: SLMath: Baker Board Room

Andrade, Rey, Ruiz


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 No Notes/Supplements Uploaded
Video/Audio Files

Andrade, Rey, Ruiz

H.264 Video Team_3.mp4 128 MB video/mp4 rtsp://videos.msri.org/data/000/023/917/original/Team_3.mp4 Download
Troubles with video?

Please report video problems to itsupport@slmath.org.

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