Formalizing outline of combinatorial proof of Brouwer fixed point theorem

Question

I'm trying to get a complete combinatorial proof of Brouwer's fixed-point theorem using the outline presented by Wikipedia. In this outline, we take the $n$-simplex $\Delta_n$ and for every triangulation, the color of every vertex $P=(P_0,..,P_n)$ is an index $j$ such that $f(P)_j\leq P_j$. I know that, by Sperner's lemma, there is an $n$-dimensional simplex with vertices $(0,1,...,n)$, or a rainbow simplex, in every triangulation. Then, the text says:

"Because $f$ is continuous, this simplex can be made arbitrarily small by choosing an arbitrarily fine triangulation. Hence, there must be a point $P$ which satisfies the labeling condition in all coordinates, i.e.: $\forall \ j: f(P)_j\leq P_j$."

I'm confusing about the words "this simplex", because a simplex changes when it is triangulated, and because we may have various rainbow simplexes in the same triangulation. I've read others combinatorial proofs, as the one offered by Jacob Fox in http://math.mit.edu/~fox/MAT307-lecture03.pdf. I guess the key is to get a sequence of finer subdivisions of $\Delta_n$ and from them a sequence of rainbow simplexes, maybe like $R_1\supset R_2 \supset ...$ But I'm not sure of it. If someone could help me, I'd be grateful. Thank you!

Answer 1

The following proof presented in Sperner's Lemma by Moor Xu provides some more details and could be used to fill the gaps. Here we consider the first non-trivial case, namely $n=2$.

Proof of Brouwer's fixed point theorem for $n=2$: Since a disk is homeomorphic to a triangle, it suffices to prove that any continuous map on a triangle has a fixed point.

For a reasoning see e.g. the answer to this MSE question. Since $2$-simplices are homeomorphic we can wlog consider the following $2$-simplex.

We consider the triangle $\Delta\in\mathbb{R}^3$ with vertices $e_1 = (1, 0, 0)$, $e_2 = (0, 1, 0)$, and $e_3 = (0, 0, 1)$, i.e.

\begin{align*} \Delta = \{(a1, a2, a3) \in [0, 1]^3: a1 + a2 + a3 = 1\} \end{align*}

We suppose to the contrary that a continuous map $f : \Delta \to \Delta$ has no fixed point, i.e. there is no $a\in\Delta$ with $f(a)=a$.

We define for each triangulation $T$ of $\Delta$ a specific coloring.

• The vertices $e_1,e_2,e_3$ shall be colored with $\{1, 2, 3\}$.

• The nodes $v$ of a triangulation $T$ shall be colored according to the following rule: The color of $v$ is the minimum color $i$ such that $f(v)_i < v_i$.

This coloring is well-defined since \begin{align*} v&=(v_1,v_2,v_3)\quad&\text{with}&\quad &v_1+v_2+v_3&=1\\ f(v)&=(f(v)_1,f(v)_2,f(v)_3)\quad&\text{with}&\quad &f(v)_1+f(v)_2+f(v)_3&=1\\ \end{align*} and $f(v)\ne v$ according to our assumption, there is a minimum index $i$ such that the $i$-th coordinate of $f(v)-v$ is negative.

• Note $e_1$, $e_2$, and $e_3$ are colored pairwise differently. This holds true since they each maximize a different coordinate and hence are first negative at that coordinate.

• Furthermore, a vertex on the $e_1e_2$ edge has $a_3 = 0$, so that $f(v)-v$ has nonnegative third coordinate and is hence colored $1$ or $2$.

The same is true for the other coordinates and we can invoke Sperner's Lemma to conclude the triangulation $T$ contains a rainbow triangle.

Let $\delta(T)$ denote the maximal length of an edge in a triangulation $T$. We can construct a sequence of triangulations $T_1, T_2,\ldots$ such that $\delta(T_k) \longrightarrow 0$ as $k \longrightarrow \infty$.

We pick out a sequence of rainbow triangles $\Delta_k$. These rainbow triangles $\Delta_k$ don’t necessarily have to converge to a point, but every sequence in a compact space has a convergent subsequence. So there is some subsequence of rainbow triangles $$\Delta_{k_1}, \Delta_{k_2},\ldots$$ that converges to some point $x$.

We know that for each $i$, there are vertices $v_{i,1},v_{i,2},v_{i,3}$ of a rainbow triangle close to $x$ such that $f(v_{i,1})$ has its first coordinate less than that of $v_{i,1}$. This means that $f(x)$ has its first coordinate at most that of x. The same is true for the second and third coordinates and we conclude $f(x) = x$.

Here we have the situation that \begin{align*} f(v_{i,j})_j<(v_{i,j})_j\qquad j=1,2,3\qquad\text{and}\qquad \lim_{i\to\infty} v_{i,j}=x\qquad j=1,2,3 \end{align*} this implies $(f(x))_j\leq x_j$, $j=1,2,3$ by continuity, contradicting the assumption there is no fixed point.