This post is my writeup of the exercises in this post.
1.(1-D Sperner's lemma) Consider a path built out of n edges as shown. Color each vertex blue or green such that the leftmost vertex is blue and the rightmost vertex is green. Show that an odd number of the edges will be bichromatic.
With length two there this is clearly true. When we add a node between two other nodes, if it is a different colour to both adjacent nodes then two new bichromatic vertices are introduced, else the number of such vertices stays the same. All sequences can be generated by successive addition of nodes in this way therefore by induction there will always be an odd number of bichromatic vertices.
2.(Intermediate value theorem) The Bolzano-Weierstrass theorem states that any bounded sequence in \(\mathbb{R}^n\) has a convergent subsequence. The intermediate value theorem states that if you have a continuous function \(f:[0,1]\rightarrow\mathbb{R}\) such that \(f(0)\leq 0\) and \(f(1)\geq 0\), then there exists an \(x\in[0,1]\) such that \(f(x)=0\). Prove the intermediate value theorem. It may be helpful later on if your proof uses 1-D Sperner's lemma and the Bolzano-Weierstrass theorem.
You can map the continuous function \(f(x)\) to a path of the kind found in Question 1 of length n+1 by evaluating \(f(x)\) at \(x=0\), \(x=1\) and n-1 equally spaced divisions between these two points and setting a node as blue if \(f(x)<0\) else as green.
By Sperner's Lemma there is an odd, and therefore non-zero number of b-g vertices. You can then take any b-g pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of \(x\) - only one where \(f(x)\) is below zero - that are \(\frac{1}{n^k}\) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence \(f(x)\) of initial nodes x we get a sequence that, by B-W, has a sub-sequence which converges to zero. By continuity we have proved the existence of an \(x\) such that \(f(x)=0\).
3.
(1-D Brouwer fixed point theorem) Show that any continuous function \(f:[0,1]\rightarrow[0,1]\) has a fixed point (i.e. a point \(x\in[0,1]\) with \(f(x)=x\)). Why is this not true for the open interval \((0,1)\)?
Define \(g(x)=f(x)-x\). At \(x=0\), \(g(x)\geq 0\). At \(x=1\), \(g(x)\leq 0\). By 2. there exists an \(x\) such that \(g(x)=0\) since \(g(x)\) is continuous if \(f(x)\) is continuous. Where \(g(x)=0\), \(f(x)=x\) therefore \(f(x)\) has a fixed point in \([0,1]\). This is not true because for the open interval \((0,1)\) because the fixed point may be exactly at 0 or 1, for example \(f(x)=\frac{x}{2}\) has no fixed point in \((0,1)\).
4.
(2-D Sperner's lemma) Consider a triangle built out of \(n^2\) smaller triangles as shown. Color each vertex red, blue, or green, such that none of the vertices on the large bottom edge are red, none of the vertices on the large left edge are green, and none of the vertices on the large right edge are blue. Show that an odd number of the small triangles will be trichromatic.
First let's separate all of the red nodes into groups so that within each group you can get to any other node in that group only passing through red nodes, but not to red nodes in any other group.
Now, we trace out the paths that surround these groups - they immediately look like the paths from Question 1 so this feels like a good start. More precisely, we draw out the paths such that each vertex forms one side of a triangle that has a blue node at its opposite corner. Note that you can have multiple paths stemming from the same group if the group touches the side of the larger triangle, or if it has internal holes.
Now we have this set of paths we can split them into three kinds. The first is loops, which arise when you have a group which never touches the edge of the larger triangle, or inside 'holes' in large groups. These can be seen as a path starting and finishing at the same node. They therefore have an even number of b-g vertices. The second kind is those that begin at the edge of the large triangle and end at the same edge. These paths begin and end on the same colour and therefore also have an even number of b-g vertices. Finally and most importantly there is a kind of path that goes from one edge to the other -in the case of the reds, the left edge to the right edge. This will happen once with the group that includes the top red node, and if any other group spans the larger triangle then it will generate two more of these paths. Sperner's lemma tells us that these will have an odd number of b-g vertices and we know that there will be an odd number of such paths, so this final type generates an odd number of total b-g vertices.
By the way that we have defined these paths, the total number of r-g-b triangles is equal to the number of g-b vertices on the paths in the set generated above. This number is the sum of an odd number from the spanning paths and a series of even numbers from the other paths, giving an odd overall number of r-g-b vertices, proving number 4 (as long as I haven't made an error in categorizing the paths).
5.
Color the all the points in the disk as shown. Let \(f\) be a continuous function from a closed triangle to the disk, such that the bottom edge is sent to non-red points, the left edge is sent to non-green points, and the right edge is sent to non-blue points. Show that \(f\) sends some point in the triangle to the center.
If we subdivide the triangle into a net with n nodes along each side, we know that each subdivision will result in a net with an odd and therefore non-zero number of three-colour triangles. We must be careful because we cannot assume that these triangles will themselves contain a point that maps to the centre because the smaller triangles do not necessarily fulfil the condition that the points along the side sof the triangle are not of the colour of the opposite vertex. Nonetheless, we can still, by increasing n, generate a sequence of points in the centre of these triangles that map to a point a distance \(d\) away from the centre. This sequence is bounded and therefore has a convergent subsequence. It seems that continuity should constrain this sequence from converging anywhere other than \(d=0\) but I need to do more work to show why/if this is true.
6.
Show that any continuous function \(f\) from a closed triangle to itself has a fixed point.
As in 3. we consider the vector \(\textbf{g}(\textbf{x})=\textbf{f}(\textbf{x})-\textbf{x}\) where \(\textbf{x}\) is the position on the closed triangle in \(\mathbb{R}^2\). Mapping this to the disk we see that the bottom line of the triangle must map to the upper half of the disk, the top corner must map to the bottom sixth and so by colouring points of the triangle according to the direction of \(\textbf{g}(\textbf{x})\) we get a net as seen in 4. and by 5. we know that there exists a point that maps to the centre, therefore, by the same logic as 2., any continuous function from the closed triangle to itself has a fixed point.
7.
(2-D Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of \(\mathbb{R}^2\) to itself has a fixed point. (You may use the fact that given any closed convex subset \(S\) of \(\mathbb{R}^n\), the function from \(\mathbb{R}^n\) to \(S\) which projects each point to the nearest point in \(S\) is well defined and continuous.)
We take our closed convex set \(S\) that has the bounded function \(h:S\rightarrow S\). We take a triangle \(T\) that covers \(S\) so that any point in \(S\) is also in \(T\).
Now we define a function \(h':T\rightarrow T\) such that \((h'(x)=h(c_s(x))\) where \(c_s(x)\) is the function that maps \(x\) to the nearest point in \(S\).
By 6. we know that \(h'\) has a fixed point since \(c_s\) is continuous. We know that the fixed point of \(h'\) cannot lie outside \(S\) beacuse the range of \(h'\) is \(S\). This means \(h'\) has a fixed point within \(S\) and since for \(x\in S\), \(h(x)=h'(x)\), \(h\) has a fixed point.
8.
Reflect on how non-constructive all of the above fixed-point findings are. Find a parameterized class of functions where for each \(t\in[0,1],f_t:[0,1]\rightarrow[0,1]\), and the function \(t\rightarrow f_t\) is continuous, but there is no continuous way to pick out a single fixed pont from each function (i.e. no continuous function \(g\) such that \(g(t)\) is a fixed point of \(f_t\) for all \(t\)).
The cleanest example I can find is \(f_t(x)=\frac{1}{1+e^{10(t-x)}}\)
9.
(Sperner's lemma) Generalize exercises 1 and 4 to an arbitrary dimension simplex.
Now things are starting to get tricky but we can still use the intuition from 4., but we'll need to be more explicit. We assume that we know that an odd number of small simplices are (n)-chromatic for an n-1 dimensional simplex. Now take one vertex of our n simplex and for each facet add nodes of the same colour according to a left hand rule so that exactly one n+1 dimension simplex is added which is attached to the vertex we began with and we retain the property that no facet constains a node the same colour as its opposite vertex.
Now w