A direct proof of Shapley-Sperner's lemma based on the KKMS lemma (Q1996898)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A direct proof of Shapley-Sperner's lemma based on the KKMS lemma |
scientific article |
Statements
A direct proof of Shapley-Sperner's lemma based on the KKMS lemma (English)
0 references
28 February 2021
0 references
Let \(N=\{0,1,\dots,n\}\) and \(e_{0,}e_{1},\dots,e_{n}\) be unit vectors in \( R^{n+1}.\) The standard \(n\)-simplex, denoted by \(\Delta _{n}\), is \( co\{e_{0,}e_{1},\dots,e_{n}\}\). For \(S=\{i_{0},\dots,i_{m}\}\subset N\), \(\Delta _{S}=co\{e_{i_{0}},\dots,e_{i_{m}}\}\) is a face of \(\Delta _{n}\). The Shapley-Sperner (SS) lemma claims that for any subdivision \(T\) of \( \Delta _{n}\) and a set-valued Sperner labeling \(l\) there is at least one balanced labeled subsimplex. The authors show that SS lemma is equivalent to Knaster-Kuratowski-Mazurkiewicz-Shapley (KKKS) lemma: Let \(\{C_{S}:S\subset N\}\) be a family of closed subsets of \(\Delta _{n}\) such that \(\Delta _{J}\subset \cup _{S\subset J}C_{S}\) for all \(J\subset N\). Then, there exists a balanced family \(\beta \subset N\) such that \(\cap _{S\subset J} C_{S}\neq \emptyset .\) Thus, the SS lemma can be regarded as a combinatorial analog of the KKMS lemma.
0 references
simplex subdivision
0 references
Sperner labeling
0 references
Shapley-Sperner lemma
0 references
Knaster-Kuratowski-Mazurkiewicz-Shapley lemma
0 references
0 references