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
    0 references
    0 references
    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

    Identifiers