/Exposé /Talk/
Sperner's lemma states that if a labelling of the vertices of a triangulation $K$ of the $d$-simplex $\Delta^d$ with labels $1, 2, ..., d+1$ has the property that (i) each vertex of $\Delta^d$ receives a distinct label, and (ii) any vertex lying in a face of $\Delta^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).
Tibor Gallai observed that Sperner's Lemma was equivalent to the claim that certain graphs associated to the triangulations of $\Delta^d$ are $(d+2)$-chromatic, and he asked in 1969 whether these graphs are in fact $(d+2)$-critical. (The question is included as Problem 9.14 in Jensen and Toft's collection \emph{Graph Coloring Problems}.)
In this talk, we show that the answer is affirmative for $d\leq 2$ (as already proved by Gallai); for every $d\geq 3$, however, we answer Gallai's question in the negative by constructing an infinite family of examples where no labelling with the requested property exists. The construction is based on the properties of a convex $4$-polytope which had been used earlier to disprove a claim of Theodore Motzkin on neighbourly polytopes.
Joint work with Matěj Stehlík and Riste Škrekovski
[Tomas Kaiser ] (Faculty of Applied Sciences, Pilsen )
https://home.zcu.cz/~kaisert/
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .