Sperner labellings: A combinatorial approach
type: Item
instance of: scholarly article
title: Sperner labellings: A combinatorial approach
zbMATH Open document ID: 1108.52012
author: Frédéric Meunier
published in: Journal of Combinatorial Theory. Series A
publication date: 2006-12-07T00:00:00Z
review text: The author defines a \(d\)-dimensional polytopal body as a pure \(d\)-dimensional polytopal complex \(P\) such that the boundary complex \(B(P)\) is strongly connected and each polytope of \(B(P)\) having dimension \(d-2\) belongs to exactly two \((d-1)\)-polytopes of \(B(P)\). Suppose \(P\) is a polytopal body such that \(B(P)\) has \(n\) vertices. A triangulation \(T\) of the underlying space \(\| P\| \) induces a triangulation of the polytopes in \(B(P)\). If we label the vertices of \(T\) in such a way that each vertex of \(B(P)\) gets a unique label in \(\{ 1, 2, \dots, n \}\), each vertex of \(T\) in the interior of \(\| P\| \) gets any label \(\{ 1, 2, \dots, n \}\), and each other vertex of \(T\) gets a label of one of the minimal polytopes of \(B(P)\) it belongs to, then we get a Sperner labelling of \(T\). A fully-labelled simplex in \(T\) is a simplex whose labels are all distinct. The degree \(\text{ deg}_C (v)\) of a vertex \(v\) of a polytopal complex is the number of edges of \(C\) that \(v\) belongs to. The main theorem of the paper is as follows: Let \(P\) be a \(d\)-dimensional polytopal body whose boundary complex \(B(P)\) has vertices \(\{ v_1, v_2, \dots, v_n \}\), and let \(T\) be a triangulation of \(\| P\| \). Any Sperner labelling of \(T\) contains at least \(n + \lceil {{ \min_j \text{ deg}_{ B(P) } (v_j) } \over { d }} \rceil - d - 1\) fully-labelled \(d\)-simplices such that any pair of these fully-labelled simplices receives two different labellings. This result generalizes De Loera-Peterson-Su's proof of Atanassov's conjecture, namely the special case that \(P\) consists of all faces of a polytope [\textit{J. A. De Loera, E. Peterson} and \textit{F. E. Su}, J. Comb. Theory, Ser.~A 100, No. 1, 1--26 (2002; Zbl 1015.05089)]. The latter result, in turn, generalizes the classical Sperner Lemma.
reviewed by: Matthias Beck
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 5078225
zbMATH Keywords: chain map
zbMATH Keywords: fully-labelled simplex
zbMATH Keywords: labelling
zbMATH Keywords: polytopal body
zbMATH Keywords: polytope
zbMATH Keywords: Sperner's lemma
zbMATH Keywords: triangulation
MaRDI profile type: Publication
full work available at URL: j.jcta.2006.01.006
OpenAlex ID: W1972642911
cites work: Q4892306
cites work: A polytopal generalization of Sperner's lemma
cites work: Hilbert bases, unimodular triangulations, and binary covers of rational polyhedral cones
cites work: Q3827224
cites work: Lectures on Polytopes
DOI: 10.1016/J.JCTA.2006.01.006
description: scientific article; zbMATH DE number 5078225