[gt.go] - "Criticality in Sperner's Lemma" by Tomas Kaiser

/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 )

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 ] .