5
$\begingroup$

Wikepedia KKM says that Brouwer fixed-point theorem, Sperner's lemma, and Knaster–Kuratowski–Mazurkiewicz lemma are equivalent.

In "A course of topological combinatorics", I find a proof that Sperner implies Brouwer. I am wondering is there a proof that Sperner implies KKM?

$\endgroup$

1 Answer 1

6
$\begingroup$

Consider the $k$th barycentric division, which is a triangulation, $T^k$ of $\Delta_n:=\{(x_1,...,x_{n+1}): x_i\ge 0, \sum x_i=1\}$.

We color each vertex $v$ of $T_k$ by minimum $i$ such that $v_i\neq 0$ and $v\in A_i$, where $A_1,...,A_n$ are the closed sets in KKM lemma. Then this coloring is a legal Sperner coloring and we know that there exists a simplex $\sigma_k$ in $T^k$ whose vertices are rainbow (in $n$ colors).

As the volume of $\sigma_k$ tends to 0 as $k$ goes to infinity, we know that there exists $z\in \Delta_n$ that is a common accumulation point of all the vertices in an infinite subsequence of $\sigma_k$ (say $\sigma_{k_\ell}$). As $A_i$ are closed and the vertices of $\sigma_k$ are rainbow, we know that $z\in\bigcap_i A_i$. (For the vertices $v(k_\ell,i)$, which are the vertices in $\sigma_{k_\ell}$ and are colored by $i$, by definition we have $v(k_\ell,i)\in A_i$, and we have $v=\lim_\ell v(k_\ell,i)$ is also in $A_i$ as $A_i$ are closed.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.