Criticality in Sperner’s lemma

Speaker: Matej Stehlik

Room: B507

Date: 26/04/2024 14:00

Abstract:

Sperner's lemma states that in any labelling of the vertices of a triangulation of a d-dimensional simplex with d+1 labels, where each vertex of the d-simplex receives a distinct label and any vertex lying in a face of the d-simplex has the same label as one of the vertices of that face, there exists a rainbow facet (one whose vertices have pairwise distinct labels). Tibor Gallai proved that in the 2-dimensional case, given any facet s of the triangulation, there is a labelling where s is the unique rainbow facet. In 1969 Gallai asked if the same property holds in higher dimensions. In this talk, I will show how a neighbourly 4-polytope discovered by Grunbaum can be used to give a negative answer to Gallai's question. I will also describe a connection to the chromatic number of graphs, which was the real motivation behind Gallai's question.