Criticality in Sperner's Lemma

MaRDI QIDQ6422930zbMATH OpenFDO

Authors Tomáš Kaiser, Matěj Stehlík, Riste Škrekovski

Publication date 9 January 2023

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial aspects of simplicial complexes (05E45)

Abstract: We answer a question posed by Tibor Gallai in 1969 concerning criticality in Sperner's lemma, listed as Problem 9.14 in the collection of Jensen and Toft [Graph coloring problems, John Wiley & Sons, Inc., New York, 1995]. Sperner's lemma states that if a labelling of the vertices of a triangulation of the $d$-simplex $Delt{a}^d$ with labels $1,2,ldots,d+1$ has the property that (i) each vertex of $Delt{a}^d$ receives a distinct label, and (ii) any vertex lying in a face of $Delt{a}^d$ has the same label as one of the vertices of that face, then there exists a rainbow facet (a facet whose vertices have pairwise distinct labels). For $dleq2$, it is not difficult to show that for every facet $sigma$, there exists a labelling with the above properties where $sigma$ is the unique rainbow facet. For every $dgeq3$, however, we construct an infinite family of examples where this is not the case, which implies the answer to Gallai's question as a corollary. The construction is based on the properties of a $4$-polytope which had been used earlier to disprove a claim of Theodore Motzkin on neighbourly polytopes.

This page was built for publication: Criticality in Sperner's Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6422930)