6
$\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$
2
  • $\begingroup$ "As the volume of σk tends to 0 as k goes to infinity, we know that there exists z∈Δn that is a common accumulation point of all the vertices in an infinite subsequence of σk" I do not understand why. In theory, if you have a black box that returns a rainbow-simplex for each $k$, it can return a rainbow simplex in a different region each time, so that the sequence does not converge. How do you know that there is a converging sub-sequence? $\endgroup$ Aug 18, 2022 at 17:13
  • 1
    $\begingroup$ That is Bolzano–Weierstrass theorem for $\mathbb{R}^n$ as $\Delta_n$ is a compact set so that each infinite sequence in it has a convergent subsequence. $\endgroup$
    – Connor
    Aug 21, 2022 at 9:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .