The -dimensional simplex is the following subset of
More generally, if is a set of vectors, then is the simplex spanned by :
Let be the standard orthonormal basis of . So, is the simplex spanned by . Any element of is represented by a vector of coordinates such that ; these are called a barycentric coordinates of . If the set is in general position then the above representation is unique and we say that is a basis for . If we write then is always a basis.
Let be in , a basis and represented (uniquely) by barycentric coordinates . We denote by the subset of (i.e., the set of non-null coordinates). Let , the -th face of is the set . A face of is an -face for some (note that this is independent of the choice of basis).
2 KKM Lemma
The main result we prove is the following:
Theorem 1 (Knaster-Kuratowski-Mazurkiewicz Lemma ).
Let be the standard simplex spanned by the standard orthonormal basis for . Assume we have closed subsets of with the property that for every subset of the following holds: the -th face of is a subset of . Then, the intersection of the sets is non-empty.
Definition 2 (Simplicial subdivision of ).
A simplicial subdivision of is a couple ; are the vertices, a finite subset of ; is a set of simplexes where each is a subset of of size . has the following properties:
The union of the simplexes in is .
If and intersect then the intersection is a face of both and .
The norm of , denoted by , is the diameter of the largest simplex in .
An -coloring of a subdivision of is a function
A Sperner Coloring of is an -coloring such that for every , that is, if is on the -th face then its color is from . For example, if is a subdivision of the standard simplex then the standard basis is a subset of and . Hence, If is a Sperner Coloring of then for all .
Theorem 3 (Sperner’s Lemma).
Let be a simplicial subdivision of and a Sperner Coloring of . Then, there is a simplex such that .
It is a standard result, for example by barycentric subdivisions, that has a sequence of simplicial subdivisions such that . We use this fact to prove the KKM Lemma:
Proof of KKM Lemma.
Let be closed subsets of as given in the lemma. We define the following function as follows:
is well defined by the hypothesis of the lemma and . Also, if then . Let be a sequence of simplicial subdivisions such that . We set the color of every vertex in to be . This is a Sperner Coloring since if is in -fact then . Therefore, by Sperner’s Lemma we have in each subdivision a simplex such that . Moreover, . By the properties of for every and every we have that . Let be the arithmetic mean of the elements of (this is an element of and thus an element of ). Since is bounded and closed we get that has a converging subsequence with a limit . Now, every set is closed, and for every we have an element of of -distance from ; thus is in .
Therefore, is in the intersection of all the sets , and that proves the assertion. ∎
- 1 B. Knaster, C. Kuratowski, and S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe, Fund. Math. 14 (1929) 132-137.
|Date of creation||2013-03-22 16:26:31|
|Last modified on||2013-03-22 16:26:31|
|Last modified by||uriw (288)|