Sperner labellings: A combinatorial approach (Q855840)

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.