Topological Fixed Point Exercises

Scott Garrabrant; SamEisenstat

This is one of three sets of fixed point exercises. The first post in this sequence is here, giving context.

1. (1-D Sperner's lemma) Consider a path built out of 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.

2. (Intermediate value theorem) The Bolzano-Weierstrass theorem states that any bounded sequence in $R^{n}$ has a convergent subsequence. The intermediate value theorem states that if you have a continuous function $f : [0, 1] \to 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

3. (1-D Brouwer fixed point theorem) Show that any continuous function $f : [0, 1] \to [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)$ ?

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.

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.

6. Show that any continuous function $f$ from 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 $R^{2}$ to itself has a fixed point. (You may use the fact that given any closed convex subset $S$ of $R^{n}$ , the function from $R^{n}$ to $S$ which projects each point to the nearest point in $S$ is well defined and continuous.)

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] \to [0, 1]$ , and the function $t \mapsto f_{t}$ is continuous, but there is no continuous way to pick out a single fixed point from each function (i.e. no continuous function $g$ such that $g (t)$ is a fixed point of $f_{t}$ for all $t$ ).

9. (Sperner's lemma) Generalize exercises 1 and 4 to an arbitrary dimension simplex.

10. (Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of $R^{n}$ to itself has a fixed point.

11. Given two nonempty compact subsets $A, B \subseteq R^{n}$ , the Hausdorff distance between them is the supremum

max {sup a \in A d (a, B), sup b \in B d (b, A)}

over all points in either subset of the distance from that point to the other subset. We call a set valued function $f : S \to 2^{T}$ a continuous Hausdorff limit if there is a sequence ${f_{n}}$ of continuous functions from $S$ to $T$ whose graphs, ${(x, y) ∣ y = f_{n} (x)} \subseteq S \times T$ , converge to the graph of $f$ , ${(x, y) ∣ f (x) ∋ y} \subseteq S \times T$ , in Hausdorff distance. Show that every continuous Hausdorff limit $f : T \to 2^{T}$ from a compact convex subset of $R^{n}$ to itself has a fixed point (a point $x$ such that $x \in f (x)$ ).

12. Let $S$ and $T$ be nonempty compact convex subsets of $R^{n}$ . We say that a set valued function, $f : S \to 2^{T}$ is a Kakutani function if the graph of $f$ , ${(x, y) ∣ f (x) ∋ y} \subseteq S \times T$ , is closed, and $f (x)$ is convex and nonempty for all $x \in S$ . For example, we could take $S$ and $T$ to be the interval $[0, 1]$ , and we could have $f : S \to 2^{T}$ send each $x < \frac{1}{2}$ to ${0}$ , map $x = \frac{1}{2}$ to the whole interval $[0, 1]$ , and map $x > \frac{1}{2}$ to ${1}$ . Show that every Kakutani function is a continuous Hausdorff limit. (Hint: Start with the case where $S$ is a unit cube. Construct $f_{n}$ by breaking $S$ into small cubes of side length $2^{- n}$ . Constuct a smaller cube of side length $2^{- n - 1}$ within each $2^{- n}$ cube. Send each small $2^{- n - 1}$ to the convex hull of the images of all points in the $2^{- n}$ cube with a continuous function, and glue these together with straight lines. Make sure you don't accidentally get extra limit points.)

13. (Kakutani fixed point theorem) Show that every Kakutani function from a compact convex subset of $S \subseteq R^{n}$ to itself has a fixed point.

Please use the spoilers feature - the symbol '>' followed by '!' followed by space -in your comments to hide all solutions, partial solutions, and other discussions of the math. The comments will be moderated strictly to hide spoilers!

I recommend putting all the object level points in spoilers and leaving metadata outside of the spoilers, like so: "I think I've solved problem #5, here's my solution <spoilers>" or "I'd like help with problem #3, here's what I understand <spoilers>" so that people can choose what to read.

Proof of #4, but with unnecessary calculus:

Not only is there an odd number of tricolor triangles, but they come in pairs according to their orientation (RGB clockwise/anticlockwise). Proof: define a continuously differentiable vector field on the plane, by letting the field at each vertex be 0, and the field in the center of each edge be a vector of magnitude 1 pointing in the direction R->G->B->R (or 0 if the two adjacent vertices are the same color). Extend the field to the complete edges, then the interiors of the triangles by some interpolation method with continuous derivative (eg. cosine interpolation).

Assume the line integral along one unit edge in the direction R->G or G->B or B->R to be 1/3. (Without loss of generality since we can rescale the graph/vectors to make this true). Then a similar parity argument to Sperner's 1d lemma (or the FTC) shows that the clockwise line integral along each large edge is 1/3, hence the line integral around the large triangle is 1/3+1/3+1/3=1.

By green's theorem, this is equal to the integrated curl of the field in the interior of the large triangle, and hence equal (by another invocation of green's theorem) to the summed clockwise line integrals around each small triangle. The integrals around a unicolor or bicolor triangle are 0 and -1/3 + 1/3 + 0 = 0 respectively, leaving only tricolor triangles, whose integral is again 1 depending on orientation. Thus: (tricolor clockwise) - (tricolor anticlockwise) = 1. QED.

As a physicist, this is my favorite one for obvious reasons :)

Generalized to n dimensions in my reply to Adele Lopez's solution to #9 (without any unnecessary calculus :)

Just to get things started, here's a proof for #1:

Proof by induction that the number of bicolor edges is odd iff the ends don't match. Base case: a single node has matching ends and an even number (zero) of bicolor edges. Extending with a non-bicolor edge changes neither condition, and extending with a bicolor edge changes both; in both cases the induction hypothesis is preserved.

Here's a more conceptual framing:

If we imagine blue as labelling the odd numbered segments and green as labelling the even numbered segments, it is clear that there must be an even number of segments in total. The number of gaps between segments is equal to the number of segments minus 1, so it is odd.

Cleanest solution I can find for #8:

$f_{t} (x) = \frac{1}{1 + e^{10 (t - x)}}$

Also, if we have a proof for #6 there's a pleasant method for #7 that should work in any dimension:

We take our closed convex set $S$ that has the bounded function $h : S \to S$ . We take a triangle $T$ that covers $S$ so that any point in $S$ is also in $T$ .

Now we define a new function $h^{'} : T \to 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$ because 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.

On my approach:

I constructed a large triangle around the convex shape with the center somewhere in the interior. I then projected each point in the convex shape from the center towards the edge of the triangle in a proportional manner. ie. The center stays where it is, the points on the edge of the convex shape are projected to the edge of the triangle and a point 1/x of the distance from the center to the edge of the convex shape is 1/x of the distance from the center to the edge of the triangle.

Clarifying question for #9:

How does the decomposition into segments/triangles generalize to 3+ dimensions? If you try decomposing a tetrahedron into multiple tetrahedra, you actually get 4 tetrahedra and 1 octahedron, as shown here.

EDIT: answered my own question:

You can decompose an octahedron into 4 tetrahedrons. They're irregular, but this is actually fine for the purpose of the lemma.

If #4 is true, it is provable:

If #4 is true, changing the color of a single node (except to forbidden colors on edges) cannot change the parity of the trichromatic triangle count, and this would be checkable through a finite case analysis of graphs of size <=7. Given that lemma, we can recolor one corner to red, the remainder of one large edge blue and the remaining nodes green, producing the odd count 1.

#8:

We are looking for a surface [0,1]²->[0,1] whose intersection with the plane x=y does not contain a function of t. It suffices to show that the intersection looks like the letter s, with exactly the endpoints reaching t=0 or t=1. It suffices to show that the intersection can be any continous function of x including the points t=x=y=0 and t=x=y=1. Within each plane of constant x, define the surface as 0 for small t, 1 for large t, and rapidly rising through the plane x=y wherever we want the intersection.

Found a nice proof for Sperner's lemma (#9):

First some definitions. Call a d-simplex with vertices colored in (d+1) different colored chromatic. Call the parity of the number of chromatic simplices the chromatic parity.

It's easier to prove the following generalization: Take a complex of d-simplices that form a d-sphere: then any (d+1)-coloring of the vertices will have even chromatic parity.

Proof by induction on d:

Base d=-1: vacuously true.

Assume true for d-1: Say you have an arbitrary complex of d-simplices forming a d-sphere, with an arbitrary d+1-coloring. Choose a vertex. W.L.O.G. we will call the color of the chosen vertex blue.

Take the complex of simplices that contain this vertex. Since a sphere has no boundary or branches, this complex will be a d-ball. Delete the chosen vertex, and keep only the opposite (d-1)-simplices that are left, which will form a (d-1)-sphere, call it the shell.

We need to choose a second color, say red. We'll call a (d-1)-simplex with vertices of all d+1 colors except red an R-chromatic face, and similarly with blue.

Now, replace all the red vertices in the shell with blue vertices, so that the shell is now R-chromatic. By induction it has an even number of R-chromatic faces. Consider what happens when we reconvert a vertex on the shell back to red: since the vertex was previously blue, any R-chromatic faces will get turned into B-chromatic faces. Let r be the number of R-chromatic faces on the shell, and b be the number of B-chromatic faces. The parity of r-b will remain even as we continue this process.

Let's go back to the vertex in the center of the shell. All currently chromatic simplices with this vertex have opposite faces which are B-chromatic, since this vertex is blue. We'll flip the vertex to red, which destroys chromatic simplices with opposite B-chromatic faces and creates chromatic simplices with opposite R-chromatic faces. Since r-b is even, the chromatic parity is preserved!

Since we've shown that arbitrary recoloring of vertices preserves the chromatic parity, it's clear that the chromatic parity will be even for any coloring.

Corollary: Sperner's lemma

Start with a d-simplex which has been divided into d-simplices, and where each face of the large simplex has one color which vertices on it are forbidden from taking. Take a point of each color, and match it with a face of the simplex that that color is allowed on. Then connect that vertex to each point on that face. This will create a bunch of non-chromatic simplices. Finally, create a simplex of all of the new points. This will create one chromatic simplex.

This will form a d-sphere, and thus will have an even chromatic parity. That means the original simplex must have had odd chromatic parity.

Thanks! I find this approach more intuitive than the proof of Sperner's lemma that I found in Wikipedia. Along with nshepperd's comment, it also inspired me to work out an interesting extension that requires only minor modifications to your proof:

d-spheres are orientable manifolds, hence so is a decomposition of a d-sphere into a complex K of d-simplices. So we may arbitrarily choose one of the two possible orientations for K (e.g. by choosing a particular simplex P in K, ordering its vertices from 1 to d + 1, and declaring it to be the prototypical positively oriented simplex; when d = 2, P could be a triangle with the vertices going around counterclockwise when you count from 1 to 3; when d = 3, P could be a tetrahedron where, if you position your right hand in its center and point your thumb at the 1-vertex, your fingers curl around in the same direction in which you count the remaining vertices from 2 to 4). Then any ordering of the vertices of any d-simplex in K may be said to have positive or negative orientation (chirality). (E.g. it would be positive when there's an orientation-preserving map (e.g. a rotation) sending each of its vertices to the correspondingly numbered vertices of P.)

So here's my extension of parent comment's theorem: Any coloring of the vertices of K with the colors {1, ..., d + 1} will contain an equal number of positively and negatively oriented chromatic d-simplices—that is, the reason the number of chromatic d-simplices in K must be even is that each one can be paired off with one of the opposite (mirror) orientation. (Does this theorem have a name? If so I couldn't find it.)

Following parent comment, the proof is by induction on the dimension d. When d = 1, K is just a cycle graph with vertices colored 1 or 2. As we go around clockwise (or counterclockwise), we must traverse an equal number of 1→2 edges and 2→1 edges (i.e. oppositely oriented 1-simplices), by the time we return to our starting point.

Now let d > 1, and assume the theorem is true in the (d-1)-dimensional case. As in parent comment, we may choose any vertex v of K, and then the faces opposite to v in each d-simplex in K that contains v will, together, form a (d-1)-dimensional subcomplex K′ of K that is homeomorphic (topologically equivalent) to a (d-1)-sphere.

Suppose v has color i. We will show that changing v's color to j ≠ i will add or remove the same number of positively oriented chromatic d-simplices as negatively oriented ones: Forget, for the moment, the distinction between colors i and j—say any i or j-colored vertex of K′ has color "i-or-j." Then K′ is now d-colored, so, by inductive hypothesis, the chromatic (d-1)-simplices of K′ must occur in pairs of opposite orientation (if any exist—if none exist, v can't be part of any chromatic d-simplex regardless of its color). Consider such a pair, call them F₁ and F₂.

Now cease pretending that i and j are a single color. Since F₁ was chromatic in K′, it must have had an i-or-j–colored vertex. Suppose, WOLOG, that that vertex was actually j-colored. Then, together with i-colored v, F₁ spans a chromatic d-simplex of K, call it S₁, which we may assume WOLOG to be positively oriented. Once we change the color of v from i to j, however, S₁ will have two j-colored vertices, and so will no longer be chromatic. To see that balance is maintained, consider what happens with F₂:

If F₂'s i-or-j–colored vertex was, like F₁'s, actually j-colored, then the d-simplex spanned by F₂ and v, call it S₂, was chromatic and negatively oriented (because F₂ had opposite orientation to F₁ in K′), and thus S₂ also ceased to be chromatic when we changed v's color from i to j, balancing S₁'s loss of chromatic status. Otherwise, F₂'s i-or-j–colored vertex must have been i-colored, in which case S₂ wasn't chromatic when v was also i-colored, but changing v's color to j turned S₂ into a new d-chromatic simplex. But what is S₂'s orientation? Well, it was negative under the assumption that S₂'s i-or-j–colored vertex was j-colored and v was i-colored, and swapping the labels of a pair of vertices in an oriented simplex reverses its orientation, so, under the present assumption, S₂'s orientation must be positive! Thus the loss of S₁ as a positively oriented chromatic d-simplex is balanced by the addition of S₂ as a new positively oriented chromatic d-simplex.

If all of K's vertices are the same color, it has the same number (zero) of positively and negatively oriented chromatic d-simplices, and since this parity is preserved when we change the colors of the vertices of K one at a time, it remains no matter how we (d+1)-color K. ☐

We can relate this theorem back to Sperner's lemma using the same trick as parent comment: Suppose we are given a triangulation K of a regular d-simplex S into smaller d-simplices, and a (d+1)-coloring of K's vertices that assigns a unique color to each vertex v of S, and doesn't use that color for any of K's vertices lying on the face of S opposite to v. We form a larger simplicial complex L containing K by adding d + 1 new vertices as follows: For i = 1, ..., d + 1, place a new i-colored vertex exterior to S, some distance from the center of S along the ray that goes through the i-colored vertex of S. Connect this new vertex to each vertex of K lying in the face of S opposite from the (i+1)-colored (or 1-colored, when i = d + 1) vertex of S. (Note that none of the d-simplices thereby created will be chromatic, because they won't have an (i+1)-colored vertex.) Then connect all of the new vertices to each other.

Having thus defined L, we can embed it in a d-sphere, of which it will constitute a triangulation, because the new vertices will form a d-simplex T whose "interior" is the complement of L in the sphere. Thus we can apply our above theorem to conclude that L has equally many positively and negatively oriented chromatic d-simplices. By construction, none of L's new vertices are included in any chromatic d-simplex other than T, so K must contain an equal number (possibly zero) of positively and negatively oriented chromatic d-simplices, plus one more, of opposite orientation to T. And what is the orientation of T? I claim that it is opposite to that of S: Consider T by itself, embedded in the sphere. T's boundary and exterior (the interior of L) then constitute another chromatic d-simplex, call it U, which is essentially just a magnification of S, with correspondingly colored vertices, and so share's S's orientation. Applying our theorem again, we see that T and U must have opposite orientations*, so we conclude that K must contain exactly one more chromatic d-simplex of the same orientation as S than of the opposite orientation. (As proved in nshepperd's comment for the case d = 2.)

*The observation, that, on the surface of a sphere, the interior and exterior of a trichromatic triangle have opposite orientations, is what sent me down this rabbit hole in the first place. :)

Awesome! I was hoping that there would be a way to do this!

Some preliminary thoughts on q9:

As Jessicata pointed out, in 3-dimensions or higher, our n-hedra don't split up as nicely as in the 2d case.

That isn't the only issue: many of the surfaces of connected blocks may not correspond to the type of 2d grid that we just proved this result for and it doesn't seem trivial to figure out how to characterise what kind of grids we need to extend our result too (it will be even worse in higher dimensions)

I've found two results: firstly that if you remove a triangular face and replace it with three others (imagine allowing the surface to jut out of the page), then the trichromatic parity will be preserved. Secondly, that we can replace two triangle with four triangles

Given what I've discussed above, I'd be keen for a hint as learning enough geometry to make progress on this problem would seem to be taking me pretty far afield from maths useful for ai-risk.

Inappropriately highbrow proof of #4 (2d Sperner's lemma):

This proves a generalization: any number of dimensions, and any triangulation of the simplex in question. So, the setup is as follows. We have an n-dimensional simplex, defined by n+1 points in n-dimensional space. We colour the vertices with n+1 different colours. Then we triangulate it -- chop it up into smaller simplexes -- and we extend our colouring somehow in such a way that the vertices on any face (note: a face is the thing spanned by any subset of the vertices) of the big simplex are coloured using only the colours from the vertices that span that face. And the task is to prove that there are an odd number of little simplexes whose vertices have all n+1 colours.

This colouring defines a map from the vertices of the triangulation to the vertices of the big simplex: map each triangulation-vertex to the simplex-vertex that's the same colour. We can extend this map to the rest of each little simplex by linear interpolation. The resulting thing is continuous on the whole of the big simplex, so we have a continuous map (call it f) from the big simplex to itself. And we want to prove that we have an odd number of little simplices whose image under f spans the whole thing. (Call these "good" simplices.)

We'll do it with two ingredients. The easy one is induction: when proving this in n dimensions we shall assume we already proved it for smaller numbers of dimensions. The harder one is homology, a standard tool in algebraic topology. More precisely we'll do homology mod 2. It associates with each topological space X and each dimension d an abelian group Hd(X), and the key things you need to know are (1) that if you have f : X -> Y then you get an associated group homomorphism f* : Hd(X) -> Hd(Y), (2) that Hd(a simplex) is the cyclic group of order 2 if d=0, and the trivial group otherwise, and (3) that Hd(the boundary of a simplex) is the cyclic group of order 2 if d=0 or d = (dimension of simplex - 1) and the trivial group otherwise. Oh, and one other crucial thing: if you have f : X -> Y and g : Y -> Z then (gf)* = g*f*: composition of maps between topological space corresponds to composition of homomorphisms between their homology groups.

(You can do homology "over" any commutative ring. The groups you get are actually modules over that ring. It happens that the ring of integers mod 2 is what we want to use. A simplex is, topologically, the same thing as a ball, and its boundary the same thing as a sphere.)

OK. So, first of all suppose not only that the number of good simplices isn't odd, but that it's actually zero. Then f maps the whole of our simplex to its boundary. Let's also consider the rather boring map g from the boundary to the whole simplex that just leaves every point where it is. Now, if the thing we're trying to prove is true in lower dimensions then in particular the map gf -- start on the boundary of the simplex, stay where you are using g, and then map to the boundary of the simplex again using f -- has an image that, so to speak, covers each boundary face of the simplex an odd number of times. This guarantees -- sorry, I'm eliding some details here -- that (gf)* (from the cyclic group of order 2 to the cyclic group of order 2) doesn't map everything to the identity. But that's impossible, because (gf)*=g*f* and the map f* maps to Hn(whole simplex) which is the trivial group.

Unfortunately, what we actually need to assume in order to prove this thing by contradiction is something weaker: merely that the number of good simplices is even. We can basically do the same thing, because homology mod 2 "can't see" things that happen an even number of times, but to see that we need to look a bit further into how homology works. I'm not going to lay it all out here, but the idea is that to build the Hd(X) we begin with a space of things called "chains" which are like linear combinations (in this case over the field with two elements) of bits of X, we define a "boundary" operator which takes combinations of d-dimensional bits of X and turns them into combinations of (d-1)-dimensional bits in such a way that the boundary of the boundary of anything is always zero, and then we define Hd(x) as a quotient object: (d-dimensional things with zero boundary) / (boundaries of d+1-dimensional things). Then the way we go from f (a map of topological spaces) to f* (a homomorphism of homology groups) is that f extends in a natural way to a map between chains, and then it turns out that this map interacts with the boundary operator in the "right" way for this to yield a map between homology groups. And (getting, finally, to the point) if in our situation the number of good simplices is even, then this means that the map of chains corresponding to f sends anything in n dimensions to zero (essentially because it means that the interior of the simplex gets covered an even number of times and when working mod 2, even numbers are zero), which means that we can think of f* as mapping not to the homology groups of the whole simplex but to those of its boundary -- and then the argument above goes through the same as before.

I apologize for the handwaving above. (Specifically, the sentence beginning "This guarantees".) If you're familiar with this stuff, it will be apparent how to fill in the details. If not, trying to fill them in will only add to the pain of what's already too long a comment :-).

This is clearly much too much machinery to use here. I suspect that if we took the argument above, figured out exactly what bits of machinery it uses, and then optimized ruthlessly we might end up with a neat purely-combinatorial proof, but I regret that I am too lazy to try right now.

Rough approach for qu 6:

Join the center to each of the corners and color each segment a different color and arbitrarily coloring each ambiguous point. Radially extend the colored sections to infinity.

To prove f(x) has a fixed point consider g(x) = f(x) - x which can take values outside of the triangle. To find a fixed point, we simply need to show that g(x) will map at least one point to the center. It is easy to prove that each corner will map to the color opposite and each edge can only map to points of a different color (unless it passes through the center, in which case we would have obtained out proof). At this point the problem reduces to 5 assuming that we construct a big enough circle.

My solution for #3:

Define $g : [0, 1] \to R$ by $g (x) = f (x) - x$ . We know that $g$ is continuous because $f$ and the identity map both are, and by the limit laws. Applying the intermediate value theorem (problem #2) we see that there exists $x \in [0, 1]$ such that $g (x) = 0$ . But this means $f (x) = x$ , so we are done.

Counterexample for the open interval: consider $f : (0, 1) \to (0, 1)$ defined by $f (x) = x / 2$ . First, we can verify that if $0 < x < 1$ then $0 < x / 2 < 1 / 2 < 1$ , so $f$ indeed maps to $(0, 1)$ . To see that there is no fixed point, note that the only solution to $x / 2 = x$ in $R$ is $0$ , which is not in $(0, 1)$ . (We can also view this graphically by plotting both $y = x$ and $y = x / 2$ and checking that they do not intersect in $(0, 1)$ .)

EDIT: I've got another framing that I thought would be more useful for later problems, but I was wrong. I still think there is some value in understanding this proof as well.

In particular, look at this diagram on Wikipedia. It would be better if the whole upper triangle was blue and the whole lower triangle were red instead of just one side (you can arbitrarily decide whether to paint the rest of the diagonal blue or red). If x=0 and x=1 aren't fixed points, then they must be blue and red respectively. If we split [0,1] into n components of size 1/n, then we can see where f(x) maps each such component to and form a line of colored points as in q1. Proving this using Sperner's Lemma is then essentially the same as qu2.

Yeah, I did the same thing :)

Putting it right after #2 was highly suggestive - I wonder if this means there's some very different route I would have thought of instead, absent the framing.

I'm late, but I'm quite proud of this proof for #4:

Call the large triangle a graph and the $n^{2}$ triangles simply triangles. First, note that for any size, there is a graph where the top node is colored red, the remaining nodes on the right diagonal are colored green, and all nodes not on the right diagonal are colored blue. This graph meets the conditions, and has exactly one trichromatic triangle, namely the one at the top (no other triangle contains a red node). It is trivial to see that this graph can be changed into an arbitrary graph by re-coloring finitely many nodes. This will affect up to six triangles; we say that a triangle has changed iff it was trichromatic before the recoloring but not after, or vice versa, and we shall show that re-coloring any node leads to an even number of triangles being changed. This proves that the number of trichromatic triangles never stops being odd.

Label the three colors $x, y$ , and $z$ . Let $v$ be the node being recolored, wlog from $x$ to $y$ . Suppose first that $v$ has six neighbors. It is easy to see that a triangle between $v$ and two neighbors has changed if and only if one of the neighbors has color $z$ and the other has color $x$ or $y$ . Thus, we must show that the number of such triangles is even. If all neighbors have color $z$ , or if none of them do, then no triangles have changed. If exactly one node has color $z$ , then the two adjacent triangles have changed. Otherwise, let $j$ and $k$ denote two different neighbors of color $z$ . There are two paths using only neighbors of $v$ between $j$ and $k$ . Both start and end at a node of color $z$ . By the 1-D Sperner Lemma (assuming the more general result), it follows that both paths have an even number of edges between nodes of color $z$ and ${x, y}$ ; these correspond to the triangles that have changed.

If $v$ is a node on one of the graph's boundaries changing color from $x$ to $y$ , it has exactly 4 neighbors and three adjacent triangles. The two neighbors that are also on the boundary cannot have color $z$ , so either none, one, or both of the ones that aren't do. If it's none, no triangle has changed; if it's one, the two neighboring triangles have changed; and if it's both, then the two triangles with two nodes on the graph's boundary have changed.

Here's the rough idea for 5 (not a full-proof)

The bottom edge must stick in the blue and green sections meaning that if we were to divide the edge in n and see where these points map to, we would find that it would be blue or green and similarly the other edges would match the limitations in q4. If we look at the right corner, we see that the bottom edge maps to green or blue and the right edge maps to green or red, so the bottom corner must be in green. Similarly the other corners match the requirements of q4.

This lets us find a smaller trichromatic triangle. We can repeat this process an arbitrary number of times. Consider the range of possible x and y co-ordinates of elements in these triangles. Each time this will reduce by a particular factor, so we can see that the range of each co-ordinate will approach 0. I'll leave it to the reader to show that this means that these ranges converge to a point. I'll also leave it to the reader to show that each trichromatic sub-triangle must contain the center (you may want to look up winding numbers).

I've realised that you've gotta be careful with this method because when you find a trichromatic subtriangle of the original, it won't necessarily have the property of only having points of two colours along the edges, and so may not in fact contain a point that maps to the centre.

This isn't a problem if we just increase the number n by which we divide the whole triangle instead of recursively dividing subtriangles. Unfortunately now we're not reducing the range of co-ords where this fixed point must be, only finding a triad of arbitrarily close points that map to a triangle surrounding the centre. You can, for example, take the centre point of the first of these triangles (with some method of numbering to make the function definite) for each value of $n = 1, 2, 3..$ as a sequence in $R^{2}$ . This must have a convergent sequence which should converge to a point that maps to the centre but I can't prove that last stage.

Yeah, you're right. That breaks the proof. I don't know how to deal with it yet.

Here's a solution to 4:

We will first prove a lemma that all connected groups of green blocks that are completely surrounded by red or blue blocks will produce an even number of trichromatic triangles. We will then augment the triangle by adding an extra blue row on the bottom and an extra red side on the right such that we now have would what be a triangle if it weren't missing the bottom right corner. This will mean that all green blocks will now be surrounded so we'll have an even number of trichromatic triangles, but we have added exactly one additional such triangle, so that the original has an odd number.

------

Proof of Lemma:

A trivial variant of 1-d Sperner's Lemma is that if we start and finish on the same colour, we get an even number of bichromatic edges. For any block that is completely surrounded by red and blue blocks, we apply this variant to show that there is an even number of bichromatic edges on the outside that then translates to an even number of trichromatic triangles.

EDIT: Actually, there is one case we can run into which is tricky and that is something like:

R R R R R

R G G G R

R G R B R

R G G G R

R R R R R R

To see how to solve this case, read how to solve tricky interior cases below.

END EDIT

Thick interior blocks work similarly, but we can run into weird scenarios such as a blue and a red surrounding by green block:

g g g

g b r g

g g g

We might also run into something like this (ie. a three-spoked shape that is blue at the center and red on the sides surrounded by green).

g g g

g r g g

g b r g

g r g g

g g g

For these weird shapes we can still trace a path around this interior section, we just include going both down and up a spoke in our path (thanks Hoagy!). So the interior sections are also even.

Strategies that I've found helpful:

If something doesn't seem tractable, try flipping between algebraic and geometric interpretations of a problem. Problems 1 and 3 fell to this approach.

Specific solutions (or suggestive handwaving):

Problem 1:

I thought of it like parity - going left to right, each unichromatic edge doesn't change the color, while each bichromatic edge does. So to have an overall change, we need either 1 bichromatic edge, or 3 (1 and 2 that cancel), or 5 (1 and 4 that cancel)...

Problem 2:

I couldn't understand this one at first. After checking Wikipedia, I think that $R_{n}$ refers to the space that each point in the sequence lies within. An example of a finite sequence in $R_{2}$ would then be $(1, 2), (3, 1), (5, 3)$

Problem 3:

Consider the unit square. We need to draw one continuous line, going from left to right, that covers the entire vertical extent of the square. No matter how you do that, you need to cross the diagonal line from the bottom left to the top right.

Why? Because you need to touch the top and the bottom edges. You can't do that at the bottom-left or top-right corners, since then you'd touch the diagonal line. But then the point where you touch the top edge is entirely within the top triangle, and it cannot touch the bottom edge without entering the bottom triangle. Switching between triangles is identical to crossing the diagonal line.

As for why this isn't true if the set is open rather than closed: if we exclude the edges from our consideration of "does it intersect the diagonal", then it's fairly trivial to construct a curve that stays inside one triangle and has a codomain of (0,1). $f (x) = x^{2}$ should work.

#8 actually comes up in physics:

in the field of nonlinear dynamics (pretty picture, actual wikipedia). The fact that continuous changes in functions can lead to surprising changes in fixed points (specifically stable attractors) is pretty darn important to understanding e.g. phase transitions!

Does this work for #7? (and question) (Spoilers for #6):

I did #6 using 2D Sperner's lemma and closedeness. Imagine the the destination points are colored [as in #5, which was a nice hint] by where they are relative to their source points - split the possible difference vectors into a colored circle as in #5 [pick the center to be a fourth color so you can notice if you ever sample a fixed point directly, but if fixed points are rare this shouldn't matter], and take samples to make it look like 2d Sperner's lemma, in which there must be at least one interior tri-colored patch. Define a limit of zooming in that moves you towards the tri-colored patch, apply closedness to say the center (fixed) point is included, much like how we were encouraged to do #2 with 1D Sperner's lemma.

To do #7, it seems like you just need to show that there's a continuous bijection that preserves whether a point is interior or on the edge, from any convex compact subset of R^2 to any other. And there is indeed a recipe to do this - it's like you imagine sweeping a line across the two shapes, at rates such that they finish in equal time. Apply a 1D transformation (affine will do) at each point in time to make the two cross sections match up and there you are. This uses the property of convexity, even though it seems like you should be able to strengthen this theorem to work for simply connected compact subsets (if not - why not?).

EDIT: (It turns out that I think you can construct pathological shapes with uncountable numbers of edges for which a simple linear sweep fails no matter the angle, because you're not allowed to sweep over an edge of one shape while sweeping over a vertex of the other. But if we allow the angle to vary slightly with parametric 'time', I don't think there's any possible counterexample, because you can always find a way to start and end at a vertex.)

Then once you've mapped your subset to a triangle, you use #6. But.

This doesn't use the hint! And the hints have been so good and educational everywhere I've used them. So what am I missing about the hint?

An attempt at problem #1; seems like there must be a shorter proof.

The proof idea is "If I flip a light switch an even number of times, then it must be in the same state that I found it in when I'm finished switching."

Theorem. Let $G = (V, E)$ e a path graph on $n$ ertices with a vertex $2$ oloring $c : V \mapsto {0, 1}$ uch that if $d e g (u) = d e g (v) = 1$ hen $c (u) \neq c (v)$ Let $S := {e \in E ∣ e$ s bichromatic $}$ Then $| S |$ s odd.

Proof. By the definition of a path graph, there exists a sequence ${⟨ v_{k} ⟩}_{1 < k \leq n}$ ndexing $V (G)$ An edge $e_{k} = {v_{k}, v_{k + 1}}$ s bichromatic iff $c (v_{k}) \neq c (v_{k + 1})$ A subgraph $H$ f $G$ s a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of $G$ The color of a state is the color of its vertices. There exists a subsequence of $⟨ v_{k} ⟩$ ontaining the least term of each state; the index of a state is equal to the index of its least term in this subsequence.

Note that none of the states with even indexes are the same color as any of the states with odd indexes; hence all of the states with even indexes are the same color, and all of the states with odd indexes are the same color.

For each state $H$ there exists a subsequence of $⟨ v_{k} ⟩$ orresponding to the vertices of $H$ and the least term of each subsequence is either $v_{1}$ r some $v_{k}$ hat is the greatest term in a bichromatic edge. Thus the number of states in $G = 1 + | S |$

By contradiction, suppose that $| S |$ s even. Then the number of states is odd, and the first and last states are the same color, so the terminal vertices of $G$ re the same color, contrary to our assumption that they are different colors. Thus $| S |$ ust be odd.

:::

Turning each node but the last blue from left to right conserves the parity of the bichromatic edge count at each step until it is still odd at the end.

I'm stuck part-way through on #4 - I assume there is a way to do this without the exhaustive search I'm running into needing.

I'm going to try (nested) induction. Define triangles by side size, measured in nodes.

Induction base step: For n=2, there must be exactly one trichromatic edge.

Induction step: If there are an odd number of tri-chromatic edges for all triangles n=x, we must show that this implies the same for n=x+1.

We create all possible new triangles by adding x+1 nodes on one of the sides, then allow any of the previous x nodes on that side to change. Without loss of generality, assume we add x+1 edges to the bottom (non-red) side. These must be green or blue. The previous layer can now change any number of node-colors. We now must prove this by induction on color changes of nodes in the second-to-bottom layer to be red. (If they flip color otherwise, it is covered by a different base case.)

First, base step, assume no nodes change color. Because the previous triangle had an odd number of trichromatic edges, and the new edge is only green+blue, no new trichromatic edges were created.

Induction step: There is an x+1 triangle with an odd number of trichromatic vertices, and one node in the second-to-bottom layer changes to red. This can only create a new tri-cromatic triangle in one of the six adjacent triangles. We split this into (lots of) cases, and handle them one at a time.

(Now I get into WAY too many cases. I started and did most of the edge-node case, but it's a huge pain. Is there some other way to do this, presumably using some nifty graph theory I don't know, or will I need to list these out? Or should I not be using the nested induction step?)

Pointers welcome!

You can use 1d-Sperner to deal with all the cases effectively.

Here's a messy way that at least doesn't need too much exhaustive search:

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).

I hope this makes sense, let me know if it doesn't or has errors :)

I am having trouble figuring out why #2 needs / benefits from Sperner's Lemma.

But I keep going back to the proof that I'm comfortable with, which depends on connectedness, so I'm clearly missing an obvious alternative proof that doesn't need topology.

I was able to get at least (I think) close to proving 2 using Sperner's Lemma as follows:

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 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.

We can be sure that the sub-sequence does in fact converge to zero, rather than any other value because if it converges to any number |a|>0, the gradient of f(x) would have to be arbitrarily high to dip back below/above 0 for a value of x arbitrarily close by and therefore would not be a continuous function.

Comments to tighten up/poke holes in the above appreciated :)

I'm having trouble understanding why we can't just fix $n = 2$ in your proof. Then at each iteration we bisect the interval, so we wouldn't be using the "full power" of the 1-D Sperner's lemma (we would just be using something close to the base case).

Also if we are only given that $f$ is continuous, does it make sense to talk about the gradient?

"I'm having trouble understanding why we can't just fix n=2 in your proof. Then at each iteration we bisect the interval, so we wouldn't be using the "full power" of the 1-D Sperner's lemma (we would just be using something close to the base case)." - You're right, you can prove this without using the full power of Sperner's lemma. I think it becomes more useful for the multi-dimensional case.

Yeah agreed, in fact I don't think you even need to continually bisect, you can just increase n indefinitely. Iterating becomes more dangerous as you move to higher dimensions because an n dimensional simplex with n+1 colours that has been coloured according to analogous rules doesn't necessarily contain the point that maps to zero.

On the second point, yes I'd been assuming that a bounded function had a bounded gradient, which certainly isn't true for say sin(x^2), the final step needs more work, I like the way you did it in the proof below.

I hit that stumbling block as well. I handwaved it by saying "continue iterating until you have $x_{(k, B)}$ and $x_{(k, G)}$ such that $f (x_{k, B}) < 0$ , $f (x_{k, G}) \geq 0$ , and f has no local maxima or local minima on the open interval $(x_{k, B}, x_{k, G})$ ", but that doesn't work for the Weierstrass function, which will (I believe) never meet that criterion.

Here is my attempt, based on Hoagy's proof.

Let $n \geq 1$ be an integer. We are given that $f (0 / n) = f (0) \leq 0$ and $f (n / n) = f (1) \geq 0$ . Now consider the points $0 / n, 1 / n, \dots, (n - 1) / n, n / n$ in the interval $[0, 1]$ . By 1-D Sperner's lemma, there are an odd number of $j \in {0, \dots, n}$ such that $f (j / n) \geq 0$ and $f ((j - 1) / n) \leq 0$ (i.e. an odd number of "segments" that begin below zero and end up above zero). In particular, $0$ is an even number, so there must be at least one such number $j$ . Choose the smallest and call this number $j_{n}$ .

Now consider the sequence $(j_{n} / n)_{n = 1}^{\infty}$ . Since this sequence takes values in $[0, 1]$ , it is bounded, and by the Bolzano–Weierstrass theorem there must be some subsequence $(k_{n} / n)_{n = 1}^{\infty}$ that converges to some number $x \in [0, 1]$ .

Consider the sequences $(f ((k_{n} - 1) / n))_{n = 1}^{\infty}$ and $(f (k_{n} / n))_{n = 1}^{\infty}$ . We have $f ((k_{n} - 1) / n) \leq 0 \leq f (k_{n} / n)$ for each $n \geq 1$ . By the limit laws, $(k_{n} - 1) / n \to x$ as $n \to \infty$ . Since $f$ is continuous, we have $f ((k_{n} - 1) / n) \to f (x)$ and $f (k_{n} / n) \to f (x)$ as $n \to \infty$ . Thus $f (x) \leq 0$ and $f (x) \geq 0$ , showing that $f (x) = 0$ , as desired.

Ex 1

Let $V = {v_{0}, . . ., v_{n}}$ and $e_{k} := (v_{k - 1}, v_{k})$ . Given an edge $e$ , let $ϕ_{e}$ denote the map that maps the color of the left to that of the right node. Given a $k \in {1, . . ., n}$ , let $ϕ_{k} = ϕ_{e_{k}} \circ . . . \circ ϕ_{e_{1}}$ . Let $b$ denote the color blue and $g$ the color green. Let $c (k)$ be 1 if edge $e_{k}$ is bichromatic, and 0 otherwise. Then we need to show that $ϕ_{n} (b) = g ⟹ (\sum_{k = 1}^{n} c (k)) is odd$ . We'll show $(\sum_{k = 1}^{n} c (k)) is even ⟺ ϕ_{n} (b) = b$ , which is a striclty stronger statement than the contrapositive.

For $n = 1$ , the LHS is equivalent to $c (ϕ_{1}) = 1$ , and indeed $ϕ (e_{1}) (b)$ equals $g$ if $e_{1}$ is bichromatic, and $b$ otherwise. Now let $n > 1$ and let it be true for $n - 1$ . Suppose $\sum_{k = 1}^{n} c (k) is even$ . Then, if $c (e_{n}) = 1$ , that means $(\sum_{k = 1}^{n - 1} c (k)) is odd$ , so that $ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (g) = b$ , and if $c (e_{n}) = 0$ , then $(\sum_{k = 1}^{n - 1} c (k)) is even$ , so that $ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (b) = b$ . Now suppose $\sum_{k = 1}^{n} c (k) is odd$ . If $c (e_{n}) = 1$ , then $(\sum_{k = 1}^{n - 1} c (k)) is even$ , so that $ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (b) = g$ , and if $c (e_{n}) = 0$ , then $(\sum_{k = 1}^{n - 1} c (k)) is odd$ , so that $ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (g) = g$ . This proves the lemma by induction.

Ex 2

Ordinarily I'd proof by contradiction, using sequences, that $inf {x \in [0, 1] | f (x) > 0}$ can neither be greater nor smaller than 0. I didn't manage a short way to do it using the two lemmas, but here's a long way.

Set $x_{0} = 0$ . Given $n \in N_{+}$ , let $G_{n}$ be a path graph of $n + 1$ vertices ${v_{n, 0}, . . ., v_{n, n}}$ , where $v_{n, k} = \frac{k}{n}$ . If for any $n$ and $k$ we have $f (v_{n, k}) = 0$ , then we're done, so assume we don't. Define $c (v, v^{'})$ to be 1 if $f (v)$ and $f (v^{'})$ have s different sign, and 0 otherwise. Sperner's Lemma says that the number of edges $e$ with $c (e) = 1$ are odd; in particular, there's at least one. Let the first one be denoted $(v, w)$ , then set $x_{n} = max {v, x_{n - 1}}$ .

Now consider the sequence $(x_{n})_{n \in N}$ . It's bounded because $x_{k} \in [0, 1]$ . Using the Bolzano-Weierstrass theorem, let $(x_{n}^{'})_{n \in N} \mapsto x^{*}$ be a convergent subsequence. Since $f (x_{k}) > 0$ for all $k \in N_{+}$ , we have $f (x^{*}) \geq 0$ . On the other hand, if $f (x^{*}) > 0$ , then, using continuity of $f$ , we find a number $x^{'} > x^{*}$ such that $f (x^{*}, x^{'}) > 0$ . Choose $n$ and $k$ such that $v_{n, k} \in (x^{*}, x^{'})$ , then $c (v_{n, j}) = 0$ for all $j < k$ , so that $x_{n} \geq v_{n, k} > x^{*}$ and then $x_{ℓ} \geq x_{n}$ for all $ℓ \geq k$ , so that $x^{*} \geq x_{n} \geq v_{n, k} > x^{*}$ , a contradiction.

Ex 3

Given such a function $f$ , let $g : [0, 1] \mapsto [- 1, 1]$ be defined by $g (x) = f (x) - x$ . We have $g (0) = f (0) - 0 \geq 0 \geq f (1) - 1 = g (1)$ . If either inequality isn't strict, we're done. Otherwise, $g (0) > 0 > g (1)$ . Taking for granted that the intermediate value theorem generalizes to this case, find a root $x^{*}$ of $g$ , then $f (x^{*}) = f (x^{*}) - x^{*} + x^{*} = g (x^{*}) + x^{*} = x^{*}$ .

On your Ex. 2:

Is there something I'm missing? It seems to me that $x_{n} = v$ for all $n > 1$ .

$(v, w)$ is defined just for one particular graph. It's the first edge in that graph such that $f (v) < 0 < f (w)$ . (So it could have been called $(v_{n}, w_{n})$ ). Then for the next graph, it's a different $v$ . Basically, $x_{1}$ looks at where the first graph skips over the zero mark, then picks the last vertex before that point, then $x_{2}$ looks at the next larger graph, and if that graph skips later, it updates to the last vertex before that point in that graph, etc. I think the reason I didn't add indices to $(v, w)$ was just that there ar ealready the $v$ with two indices, but I see how it can be confusing since having no index makes it sound like it's the same value all throughout.

Ex 5 (fixed version)

Let $D$ denote the triangle. For each $n \in N$ , construct a 2-d simplex $S_{n}$ with $(n + 1)^{2}$ nodes in $D$ , where the color of a point corresponds to the place in the disk that $f$ carries that point to, then choose $x_{n}$ to be a point within a trichromatic triangle in the graph. Then $(x_{n})_{n \in N}$ is a bounded sequence having a limit point $x^{*}$ . Let $t$ be the center of the disc; suppose that $f (x^{*}) \neq t$ . Then there is at least one region of the disc that $f (x^{*})$ doesn't touch. Let $ϵ$ be the distance to the furthest side, that is, let $ϵ = max {d (f (x^{*}), G), d (f (x^{*}), R), d (f (x^{*}), B)}$ . Since the sides are closed regions, we have $ϵ > 0$ . Using continuity of $f$ , choose $δ \in R_{+}$ small enough such that $B_{d} (x^{*}, δ) \subset B_{d} (f (x^{*}), ϵ)$ . Then choose $n \in N$ large enough so that (1) all triangles in $S_{n}$ have diameter less than $\frac{δ}{2}$ and (2) $d (x_{n}, x^{*}) < \frac{δ}{2}$ . Then, given any other point $y$ in the triangle around $x_{n}$ in $S_{n}$ , we have that $d (y, x^{*}) \leq d (y, x_{n}) + d (x_{n}, x^{*}) < \frac{δ}{2} + \frac{δ}{2} = δ$ , so that $d (f (y), f (x^{*})) < ϵ$ . This proves that the triangle in $S_{n}$ does not map points to all three sides of the disc, contradicting the fact that it is trichromatic.

Ex 6

(This is way easier to demonstrate in a picture in a way that leaves no doubt that it works than it is to write down, but I tried to do it anyway considering that to be part of the difficulty.)

(Assume the triangle $T = ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ A B O$ is equilateral.) Imbed $T$ into $R^{2}$ such that $O = (0, 0)$ , $A = (- \frac{1}{2}, \frac{1}{2} \sqrt{3})$ , $B = (\frac{1}{2}, \frac{1}{2} \sqrt{3})$ . Let $f : T \mapsto T$ be continuous. Then $h : T \mapsto R^{2}$ given by $h : x \mapsto f (x) - x$ is also continuous. If $h (x) = O = (0, 0)$ then $(0, 0) = h (x) = f (x) - x ⟹ f (x) = x$ . Let $R$ be the circle with radius 2 around $O$ ; then $h (T) \subset R$ because $| | h (x) | | = | | f (x) - x | | \leq | | f (x) | | + | | x | | \leq 2$ (it is in fact contained in the circle with radius 1, but the size of the circle is inconsequential). We will use exercise 5 to show that $h$ maps a point to the center, which is $O$ , from which the desired result follows. For this, we shall show that it has the needed properties, with the modification that points on any side may map precisely into the center. It's obvious that weakening the requirement in this way preserves the result.

Rotate the disk so that the red shape is on top. In polar coordinates, the green area now contains all points with angles between $60^{\circ}$ and $180^{\circ}$ , the blue area contains those between $180^{\circ}$ and $300^{\circ}$ , and the red area those between $0^{\circ}$ and $60^{\circ}$ and those between $300^{\circ}$ and $360^{\circ}$ . We will show that $h (¯ ¯¯¯¯¯¯ ¯ A B)$ does not intersect the red area, except at the origin. First, note that we have

$h (¯ ¯¯¯¯¯¯ ¯ A B) = {f (x) - x | x \in ¯ ¯¯¯¯¯¯ ¯ A B} \subset {y - x | x \in ¯ ¯¯¯¯¯¯ ¯ A B, y \in T} = {T - x | x \in ¯ ¯¯¯¯¯¯ ¯ A B} = T - ¯ ¯¯¯¯¯¯ ¯ A B$

Since both $T$ and $¯ ¯¯¯¯¯¯ ¯ A B$ are convex combinations of finitely many points, it suffices to check all combinations that result by taking a corner from each. This means we need to check the points

$A - A$ and $B - A$ and $C - A$ and $A - B$ and $B - B$ and $C - B$ .

Which are easily computed to be

$(0, 0)$ and $(- 1, 0)$ and $(\frac{1}{2}, - \frac{1}{2} \sqrt{3})$ and $(1, 0)$ and $(0, 0)$ and $(- \frac{1}{2}, - \frac{1}{2} \sqrt{3})$

Two of those are precisely the origin, the other four have angles $270^{\circ}$ and $150^{\circ}$ and $90^{\circ}$ and $210^{\circ}$ . Indeed, they are all between $60^{\circ}$ and $300^{\circ}$ .

Now one needs to do the same for the sets $T - ¯ ¯¯¯¯¯¯ ¯ O A$ and $T - ¯ ¯¯¯¯¯¯ ¯ B O$ , but it goes through analogously.

I am sorry because I cannot figure out how to hide big formulas in a spoiler. Also the spoiler feature is somewhat broken so it adds weird tabs around formulas.

#1:

Let's count the number of blue edge ends. Each blue point inside the segment is the end of two blue edges, and the leftmost blue vertex is the end of one. Therefore, their total number is odd. On the other hand, each bichromatic edge produces one blue edge end, and each unichromatic edge produces an odd number - zero or two - of blue edge ends. Therefore, an odd number of edges are bichromatic.

#2:

Suppose $x = inf {y \in [0, 1] | f (y) \geq 0}$ . If $f (x) > 0$ then $x \neq 0$ and, since f is continuous, f stays positive in some neighborhood of x, and then x is not the infimum. Therefore, f(x) = 0.

#3:

Consider the function $g (x) = f (x) - x$ . Since $g (0) \geq 0$ and $g (1) \leq 0$ by exercise 2, there should be a point where g(x) = 0.

#8.

Consider the family of functions: $f_{t} (x) = min (max (x - t + 0.5, 0), 1)$

For t < 0.5, the only fixed point is of $f_{t}$ is 1; for t > 0.5, the only fixed point is 0.

#9.

Lemma:

Suppose a k-dimensional simplex is subdivided into smaller k-dimensional simplices and all vertices are colored into k+1 colors so that there are no vertices of color i on the i-th edge of the big simplex. Then there are an odd number of subdivision simplices whose vertices are colored in k+1 different colors.

Proof:

Induction by k. Base k=1 proved in exercise 1.

Induction step: supposed the lemma is proved for k-1, let's prove it for k.

Let us count the number of tuples (X, Y) where X is a k-1-dimensional simplex colored in colors 0, 1, ..., k-1,

Y is a k-dimensional subdivision simplex, and X is on the boundary of Y. Each properly colored simplex X inside the big simplex produces two tuples, and each simplex on the boundary produces one tuple. X can only be on the k-th edge of the big simplex, and by the inductional assumption, there are an odd number of simplices X there. So, the total number of tuples is odd. On the other hand, each k-dimensional simplex Y can be a part of either:

0 tuples;

1 tuple if all his vertices are different;

2 tuples if has vertices of colors 0,1,...,k-1 but not all his vertices are different.

Therefore, a number of k-simplices Y with all different vertices must be odd.

Follows from 9

Suppose that center is not in the image of the triangle. Let us call a set of points bichromatic if it doesn't have points of all three colors. We color each point in the triangle in the same color as its image. Then every point in the image has an open bichromatic neighborhood. Since the map is continuous, the preimage of this neighborhood is also open. So, around every point in the triangle there can be drawn an open bichromatic ball of radius r. These balls are an open cover of the triangle, let us choose a finite subcover out of them. Suppose $ϵ$ s the minimum radius in this subcover. Split the triangle into subtriangles so that the diameter of each triangle is smaller than $ϵ / 2$ By Sperner's lemma, there is a trichromatic triangle, but since its diameter is smaller than $ϵ / 2$ it lies completely inside one of the bichromatic balls. Contradiction.

#10

First, I am going to prove that a function from a unit ball $D^{n}$ o itself has a fixed point, then that any compact convex subset of $R^{n}$ s homeomorphic to a ball.

Suppose that $f : D^{n} \to D^{n}$ as no fixed point, n>1 (case n=1 was proved in exercise 3). Then I can build a retraction from $D^{n}$ nto its boundary $S^{n - 1}$

send x to the first intersection of the ray (f(x), x) with $S^{n - 1}$ Let us prove that such a rectraction cannot exist. Suppose that such a rectraction $g$ exists. Denote $i : S^{n - 1} \to D^{n}$ the inclusion map. Then $g \circ i = i d$ nd the induced homology group homorphism $g^{*} \circ i^{*}$ ust also be identity: $H^{n - 1} (S^{n - 1}) \to^{i *} H^{n - 1} (D^{n}) \to^{g *} H^{n - 1} (S^{n - 1})$

But this is impossible because $H^{n - 1} (S^{n - 1}) = Z$ and $H^{n - 1} (D^{n}) = 0$

Now let us prove that any compact convex subset X of $R^{n}$ s homeomorphic to a ball. Let us select a maximum set of affinely independent points in X. They form some k-dimensional simplex, all X lies in the affine space spanned by this simplex, and all the interior of this simplex belongs to X, because X is convex. I'll take a ball $D^{k}$ f radius $d$ side this simplex and build a homeomorphism between X and $D^{k}$ . Taking the center of the ball as the center of coordinates, define

$f (x) = x * d / r (x))$ where $r (x) = r (| | x | |)$ s the distance to the farthest point of X in the $x$ direction, if $x \neq 0$ , 0 if

Let us prove that f and its inverse are continuous. Since X is compact, it is bounded, so there is a $R > 0$ such that $r (x) \leq R$ It follows that f and its inverse $f^{- 1} (x) = x * r (x) / d$ are continuous in zero: $\forall ϵ > 0$ if $| x | < R / d * ϵ$ $| f (x) | < ϵ$ $\forall ϵ > 0$ if $| x | < d / R * ϵ$ $| f^{- 1} (x) | < ϵ .$

Now let us prove that functions are continuous in all other points. It is sufficient to prove that r(x) is the continuous on the unit sphere. (Since composition and product of continuous functions is continuous, division by bounded from below (by d) continuous function r is continuous, ||x|| is a continuous function).

Since X is convex, the tangent cone from any point of X to $D^{k}$ lies in X. So if we take a point at the distance $R$ from the center, draw a tangent cone, and go down its boundary, we get the steepest possible rate of change of r(x) with respect to x. Therefore, r is continuous.

#6, #7: follow from #10.

#11:

Suppose f has no fixed point. Distance d(a, B) is a continuous function of a, and a continuous function reaches its minimum on a compact. TxT and the graph of f are nonitersecting compact sets, therefore the Hausdorff distance $δ$ between them is positive. It is easy to see that Hausdorff metric is indeed a metric, i.e. that a triangle inequality holds for it. So if we take any continuous function g at a distance less than $δ$ from f, its Hausdorff distance to TxT will be positive, so it can have no fixed points.

#13:

Suppose $h : S \to 2^{S}$ is a Kakutani function. We already know that any compact convex subset of $R^{n}$ s homeomorphic to a simplex. Denote $g : T \to S$ he homeomorphism between a simplex T and S.

Denote $y_{1}^{k}, \dots, y_{t}^{k}$ the k-th barithentric subdivision of T. For each $y_{i}^{k},$ choose an element $h_{i}^{k} \in h (g (y_{i}^{k}))$

Define $f_{k} (x)$ $\sum_{i = 1}^{n + 1} p_{i}^{k} (g^{- 1} (x)) h_{i}^{k}$ where $p_{i}^{k}$ are the baricentric coordinates of point $g^{- 1} (x)$ n its subdivision simplex. Function $f_{k}$ s continuous, $f_{k} (g (y_{i}^{k})) = h_{i}^{k}$ and, since S is convex, the image of $f_{k}$ lies in S.

By the Brouwer fixed point theorem, $f_{k}$ as a fixed point. Since S is compact, from the infinite sequence of fixed points of $f_{k}$ e can choose a convergent subsequence.

Suppose $x_{k} \to x^{*}$ s this subsequence, $g^{- 1} (x_{k})$ lies in the simplex $y_{1}^{k}, \dots, y_{n + 1}^{k}$ and has baricentric coordinates $p_{1}^{k}, \dots, p_{n + 1}^{k}$ . Then $g^{- 1} (x_{k}) = \sum p_{i}^{k} y_{i}^{k}$ and $f_{k} (x_{k}) = \sum p_{i}^{k} h_{i}^{k}$ so

$g^{- 1} (\sum p_{i}^{k} h_{i}^{k}) = \sum p_{i}^{k} y_{i}^{k}$ (1).

Since simplices go down in diameter, $g (y_{i}^{k}) \to x^{*}$ as $x_{k} \to x^{*}$ Each $p_{i}^{k} \in [0, 1]$ s a bounded sequence, so we can, sequentially, choose a convergent subsequence out of each of them, so we can assume that $p_{i}^{k} \to p_{i}^{*}$ Similarly, we can choose a convergent subsequence out of $h_{i}^{k}$ so we assume $h_{i}^{k} \to h_{i}^{*}$ The sequence $(g (y_{i}^{k}), h_{i}^{k})$ belongs to the graph of h and converges to the point $(x^{*}, h_{i}^{*})$ Since the graph is closed, $h_{i}^{*}$ must belong to the image of $x^{*}$ Since $\sum p_{i}^{k} = 1$ for every k, $\sum p_{i}^{*} = 1.$ ince the image is convex, $\sum p_{i}^{*} h_{i}^{*}$ lso belongs to the image of $x^{*}$ On the other hand, as we remember, since equality (1) held for every k, it also holds in the limit: $g^{- 1} (\sum p_{i}^{*} h_{i}^{*}) = \sum p_{i}^{*} g^{- 1} (x^{*})$ . Hence, $\sum p_{i}^{*} h_{i}^{*} = x^{*}$ So, $x^{*}$ is the fixed point of h.

I just tried to fix all the things in your comment. You're right, weird stuff was happening :-)

Ex12

I didn't use the hint, so my solution looks different. I also don't get how the intended solution works -- you can't choose the cubes in small enough to make sure that $f$ is constant on each cube $C$ , so $f (C)$ may not be convex. This seems to kill the straight-line solution, and I didn't see a way to salvage it.

Here's what I did in one paragraph. Divide both $S$ and $T$ into cubes. For any horizontal edge $e$ in $S$ , make sure $f_{n}$ hits the centers of all cubes that $f$ touches on points within distance $ϵ$ of $e$ (where $ϵ$ is at least the diameter of a cube in $S$ ), while moving around only within those cubes. Extend $f_{n}$ to $S$ without wandering off too far, and voilà.

Proof roadmap:

Embed $S$ and $T$ into unit cubes
Cut the unit cubes into small cubes
Prove a bunch of helpful Lemmas
Define $f_{n}$ on some subset of the unit cube containing $S$
Argue that this approximates $f$ on $S$

(1) Since $S$ and $T$ are compact and hence bounded, we can scale them down such that we can consider them subspaces of the unit cubes, i.e., $S \subseteq X := [0, 1]^{d}$ and $T \subseteq Y := [0, 1]^{m}$ , where we choose $d, m$ as small as possible. (This is the abbreviated version of working with embedding functions.)

Let $n \in N_{+}$ .

(2) By cutting each interval into $n$ pieces, i.e., $[0, \frac{1}{n}], [\frac{1}{n}, \frac{2}{n}], . . . [\frac{n - 1}{n}, 1]$ , we obtain $n^{d}$ small cubes in $X$ of the form

$[\frac{j_{1}}{n}, \frac{j_{1} + 1}{n}] \times \dots \times [\frac{j_{n}}{n}, \frac{j_{n} + 1}{n}]$

where $j_{1}, . . ., j_{n} \in {0, . . ., n - 1}$ . Enumerate these cubes as $Cubes (X) := {C_{1}, . . ., C_{n^{d}}}$ . An analogous construction for $Y$ yields $Cubes (Y) := {D_{1}, . . ., D_{n^{m}}}$ .

Given any set $Q \subseteq Y$ , we define the operator $Expand$ to 'expand' $Y$ to all the cubes that it touches, i.e.,

$Expand (Q) := {D \in Cubes (Y) | D \cap Q \neq \emptyset}$

(3) We do most work via paths. This requires a bunch of Lemmas.

Lemma 1. For any connected set $C \subseteq S$ , the set $f (C)$ is connected.

Proof. Let $f (C) = U ⊔ V$ be a separation into two closed sets. Suppose first there is a point $x \in C$ not entirely contained in $U$ or $V$ . Then, $U \cap f (x)$ and $V \cap f (x)$ is a separation of $f (x)$ , contradicting the fact that $f (x)$ is convex (and hence (path)-connected.) Thus, each $f (x)$ either lies entirely in $U$ or entirely in $V$ .

Since $U$ is closed, so is $(S \times U) \cap G_{f}$ and $π_{1} ((S \times U) \cap G_{f})$ (where $G_{f}$ is the graph of $f$ ), which is simply $f^{- 1} (U)$ . (The preimage function is well-defined for $U$ and $V$ due to the result from the previous paragraph, and the projection is closed because $S$ is compact.) Analogously, $f^{- 1} (V)$ is closed. Then, $C = (C \cap f^{- 1} (V)) ⊔ (C \cap f^{- 1} (U))$ is a separation of $C$ , implying that (because $C$ is connected), one of them is the empty set. Since $U, V \subseteq f (C)$ , this implies that $U = \emptyset$ or $V = \emptyset$ .

This is only needed to prove Lemma 2.

Lemma 2. For any connected set $C \subseteq S$ , the set $Z := Expand (f (C))$ is path-connected.

Proof. The set $Z$ consists of cubes in $Y$ . Consider the graph $G$ where all cubes in $Z$ are nodes, and there is an edge between two nodes iff the cubes share at least a point. If this graph were disconnected, then there would be a minimal distance between the sets of cubes corresponding to two disconnected parts of the graph. This yields a separation of $Z$ , which is also a separation of $f (C)$ , contradicting the previous lemma. (The distance can, in fact, be lower-bounded, but it suffices to use the fact that two closed disjoint sets in a metric space have non-zero distance.) Thus, $G$ is connected. This allows us to construct a path between the center points of two arbitrary cubes in $Z$ (since there is a corresponding path in $G$ and the straight-line connection between the centers of two cubes that share at least one vertex yields a continuous path). Now, given two points $p, p^{'}$ and two cubes $D, D^{'}$ such that $p \in D \subseteq Z$ and $p^{'} \in D^{'} \subseteq Z$ , we can construct a path from $p$ to $p^{'}$ via

$p \to center (D) \to center (D^{'}) \to p^{'} .$

Lemma 3. Given $k \in N_{+}$ and any path-connected space $Z$ , all functions from $[0, 1]^{k}$ to $Z$ are homotopic.

Proof. Let $ϕ : [0, 1]^{k} \to Z$ . Define a homotopy $Φ : [0, 1] \times [0, 1]^{k} \to Z$ by the rule $Φ (t, x_{1}, . . ., x_{k}) = Φ ((1 - t) x_{1}, . . ., (1 - t) x_{k})$ . Then, $Φ (0)$ is $ϕ$ , and $Φ (1)$ is a constant map, proving that $ϕ$ is null-homotopic. Since being homotopic is an equivalence relation (and any two constant maps are trivially homotopic in a path connected space), it follows that all maps $[0, 1]^{k} \to Z$ are homotopic to each other.

(4) Let $ϵ \in R_{+}$ be a parameter that depends on $n$ . We will specify how $ϵ$ is chosen in the last part of the proof. It will have the properties that it's at least as large as the diameter of a cube and that it converges to $0$ as $n$ grows.

Let $A \subset S$ be connected. We define two operators on $A$ . The first is the set of points in $Y$ that wish for $f_{n}$ to hit on points near it. We set

$Targets (A) := {center (D) | \exists x \in B (A, ϵ) : f (x) \cap D \neq \emptyset}$

where $B (A, ϵ) = {x \in X | d (x, A) < ϵ}$ . The second is a sufficiently small subspace of $Y$ that is guaranteed to contain all points that $f$ touches on $A$ . We set $Area (A) := Expand (Targets (A))$ . Note that this set is identical to $Expand (f (B (A, ϵ)))$ , which makes it path-connected by Lemma 2.

We now want to define a partial function $f_{n} : X \to Y$ . We begin by defining it on vertices, then generalize it to specific edges, then specific faces, and so on, until we define it on all cubes $C \in Cubes (X)$ that intersect $S$ .

A vertex $v$ is defined to be a point $v \in X$ of the form

$v = (\frac{j_{1}}{n}, \frac{j_{2}}{n}, . . ., \frac{j_{n}}{n})$

for some $j_{1}, . . ., j_{n} \in N$ . The set $Area (v)$ may be empty if $v$ is too far outside $S$ , in which case we leave $f_{n}$ undefined on $v$ . If it is not empty, choose $y \in Area (v)$ arbitrarily and set $f_{n} (v) := y$ .

We now turn to edges. However, we only consider 'horizontal' edges, that is, subspaces $e \subset X$ of the form

$e = {(a, \frac{j_{2}}{n}, . . ., \frac{j_{n}}{n}) | a \in (\frac{j_{1}}{n}, \frac{j_{1} + 1}{n})}$

for some $j_{1}, . . ., j_{n} \in N$ . Let $v$ and $w$ be the two vertices of $e$ . If $f_{n}$ is undefined on either, we leave it undefined on $e$ . If not, we define it in the following. Note that this is the step where we guarantee that $f_{n}$ hits all points in the target set.

We know from Lemma 3 that there is a path $p : [0, 1] \to Area (e)$ from $f (v)$ to $f (w)$ . Since $e$ is homeomorphic to $[0, 1]$ , it's easy to transform $p$ into a 'path' $p^{'} : e \to Area (e)$ . But we can do even better and construct a path $p^{*} : e \to Area (e)$ that starts at $f_{n} (v)$ , ends at $f_{n} (w)$ , and hits all points in $Targets (e)$ on the way. (All trivial since $Area (e)$ is path-connected.) Now we simply set $f_{n} (x) = p^{*} (x) \forall x \in e$ .

We next consider all 'horizontal-vertical' faces, that is, all sets $q \subset X$ of the form

$q = {(a, b, \frac{j_{3}}{n}, . . ., \frac{j_{n}}{n}) | a \in (\frac{j_{1}}{n}, \frac{j_{1} + 1}{n}), b \in (\frac{j_{2}}{n}, \frac{j_{2} + 1}{n})}$

for some $j_{1}, . . ., j_{n} \in N$ . Let $e$ and $e^{'}$ be the two horizontal edges of $q$ . If $f_{n}$ is undefined on either, we leave it undefined on $q$ . If not, we have two paths $p : [0, 1] \to Area (q)$ and $p^{'} : [0, 1] \to Area (q)$ which implement $f_{n}$ on $e$ and $e^{'}$ , respectively. Using Lemma 3, we obtain a homotopy $F : [0, 1] \times [0, 1] \to Area (q)$ that continuously deforms $p$ into $p^{'}$ . Since our face $q$ is homeomorphic to $[0, 1] \times [0, 1]$ , it's easy to transform $F$ into a function $F^{*} : q \to Area (q)$ . Now we simply set $f_{n} (x) = F^{*} (x) \forall x \in q$ .

Now we do the same for 3-dimensional subspaces $r \subset X$ of the form

$r = {(a, b, c, \frac{j_{4}}{n}, . . ., \frac{j_{n}}{n}) | a \in (\frac{j_{1}}{n}, \frac{j_{1} + 1}{n}), b \in (\frac{j_{2}}{n}, \frac{j_{2} + 1}{n}), c \in (\frac{j_{3}}{n}, \frac{j_{3} + 1}{n})}$

where $f_{n}$ has been defined on the two horizontal-vertical faces, and so on. This way, every $k$ -dimensional subspace of this kind contains precisely two $k - 1$ -dimensional subspaces of this kind, and if we have defined $f_{n}$ on both, we can apply a construction analogous to the above to define $f_{n}$ on the $k$ -dimensional subspace. Eventually, we define $f_{n}$ on $d$ -dimensional subspaces, which are precisely our cubes. (In the case of $d$ -dimensional subspaces, the definition above doesn't pose any restriction; it coincides with the definition of a cube $C \in Cubes (X)$ ). Importantly, this defines $f_{n}$ on any cube $C \in Cubes (X)$ that intersects $S$ . (This is so because any vertex of this cube is within $ϵ$ of $S$ , which means that it has non-empty area. This implies that we have defined $f_{n}$ on any edge, face, and so on, of $C$ .) Thus, we end up having defined $f_{n}$ on some subspace of $X$ that includes all cubes that intersect $S$ .

The advantage of this construction is that, for any $C \in Cubes (X)$ , we know that $f (C)$ is contained in $Area (C)$ , which is the same as the union of all cubes in $Y$ that $f$ touches on points near $C$ . If we had used the homomorphic extension of $f_{n}$ instead (i.e., connecting via straight lines), we could merely guarantee that $f (C)$ is contained in the convex hull of certain points in $Y$ , which may be much larger.

(5) Having defined $f_{n}$ on a subset of $X$ that contains $S$ , we take a projection $π : Y \to T$ , and define $ϕ_{n} : S \to T$ by the rule $ϕ_{n} (x) = π (f_{n} (x))$ . It remains to show that our construction is such that the Hausdorff distance between $f$ and $f_{n}$ converges to 0 as $n \to \infty$ , then the distance between $f$ and $ϕ_{n}$ converges to $0$ as well. (To see this, note that, if $f_{n} (x)$ is within $δ$ of $f (x)$ (which lies in $S$ ), then $π$ can move it by at most $δ$ , which means that $π (f_{n} (x))$ is within $2 δ$ of $f (x)$ .)

To do this, we now explain how $ϵ$ is chosen, and then argue that the Hausdorff distance can be upper-bounded by some constant times $ϵ$ .

The issue we have to deal with is that, by default, a point on the boundary of $S$ may not have any edge close to it that is contained in $S$ . (In fact, it may not even have an edge close to it that intersects $S$ .) Thus, we would like $ϵ$ to be so large that any $ϵ$ -ball around a point in $S$ must contain a $δ$ -ball entirely contained in $S$ , where $δ$ is larger than the diameter of a cube. In that case, any $x \in S$ is within $ϵ$ of a cube entirely contained in $S$ and thus also within $ϵ$ of an edge entirely contained in $S$ .

It remains to show that we can choose $ϵ$ such that it (a) has this property and (b) converges to $0$ as a function of $n$ . To show this, we consider $ϵ \in R_{+}$ fixed, and show that $n$ eventually grows large enough for that $ϵ$ to suffice.

For every point $x \in S$ , there exists some $δ \in R_{+}$ such that $B (x, ϵ)$ contains some $δ$ -ball entirely contained in $S$ . Define a function $γ : S \to R_{+}$ that each point to the supremum of such $δ$ 's. Then, $γ$ is a continuous function from a compact set to $R_{+}$ , which means it takes on a minimum value. It now suffices to choose $n$ large enough that the diameter of a cube is smaller than this minimum. (To verify that $γ$ is continuous, take a sequence $(x_{n})_{n \in N}$ of points in $S$ , assuming that $(γ (x_{n}))_{n \in N}$ doesn't converge, and derive a contradiction.)

With this out the way, we return to the proof that $f$ is the Haudorff limit of the $f_{n}$ . This consists of showing two parts:

for any point on $G_{f}$ (the graph of $f$ ), there exists a close point on $G_{f_{n}}$ (i.e., $f_{n}$ comes sufficiently close to all points on $G_{f}$ ); and
for any point on $G_{f_{n}}$ , there exists a close point on $G_{f}$ (i.e., $f_{n}$ has no points too far away from $G_{f}$ ).

Both are now easy:

Let $(x, y) \in G_{f}$ , and let $D \in Cubes (Y)$ be a cube that contains $y$ . Let $e \subset S$ be an edge with distance at most $ϵ$ to $x$ . By construction, we have $center (D) \in Targets (e)$ , which means that there is a point $x^{'} \in e$ such that $y^{'} := f_{n} (x^{'}) = center (D)$ . Since $d (x, x^{'}) < ϵ$ and $d (y, y^{'}) < ϵ$ , the distance between $(x, y)$ and $(x^{'}, y^{'})$ converges to $0$ as $n \to \infty$ .
Let $(x^{'}, y^{'}) \in G_{f_{n}}$ , and let $D \in Cubes (Y)$ be a cube containing $y^{'}$ . Since $y^{'} \in D$ , it follows that $D \subset Area (x^{'})$ , which means there exists a point $x \in S$ such that $f (x) \cap D \neq \emptyset$ , which is to say, such that there is a $y \in D$ for which $(x, y) \in G_{f}$ . Now $d (x, x^{'}) < ϵ$ and $d (y, y^{'}) < ϵ$ , and thus the distance between $(x^{'}, y^{'})$ and $(x, y)$ again converges to $0$ as $n \to \infty$ .

Ex13

Follows from Ex11 and Ex12 :-)

Ex11

(I assume the graph of is compact; otherwise, the Hausdorff distance isn't defined, and there seem to be counter-examples to the claim of the exercise.)

Since each $f_{n}$ is a continuous function from $T$ to itself, it has a fixed point $x_{n}$ by Ex10. Then $(x_{n})_{n \in N}$ is a sequence of points in a compact space and thus has a limit point $x^{*}$ .

Let $G_{f}$ be the graph of $f$ . Assume for a contradiction that $x^{*} \notin f (x^{*})$ . Then, $(x^{*}, x^{*}) \notin G_{f}$ . Since $G_{f}$ is a compact subspace of the Hausdorff space $R^{n}$ , it is also closed. Let $O ⊊ T$ be an open set around $(x^{*}, x^{*})$ disjoint from $G_{f}$ . Then, we find an $ϵ \in R_{+}$ such that $B ((x^{*}, x^{*}), ϵ) \subseteq O$ . (This uses that $T$ is convex, otherwise the ball would exist in $R^{n}$ but could fall out of $T$ and hence $O$ .)

Choose $N \subseteq N$ infinite such that $(x_{n})_{n \in N}$ is entirely contained in $B (x^{*}, \frac{ϵ}{2})$ . Note that $(x_{n}, x_{n}) \in G_{f_{n}}$ by construction. Write $D$ for the Hausdorff distance, then $D (G_{f}, G_{f_{n}}) \geq d (G_{f}, (x_{n}, x_{n})) \geq \frac{ϵ}{2} \forall n \in N$ . This contradicts the fact that $(D (G_{f}, G_{f_{n}}))_{n \in N} converges to ⟶ 0$ , hence $x^{*} \in f (x^{*})$ .

Ex10

The entire work here is to show that a continuous function from from the standard simplex $Δ_{d}$ to itself has a fixed point. If that's done, given $S ⊊ R^{d}$ compact and convex and a continuous function $ϕ$ on $S$ , we can scale $S$ to be a subset of $Δ_{d}$ , take the continuous projection $π : Δ_{d} \to S$ , and $ϕ \circ π$ gives us a function from $Δ_{d}$ to itself. Now, a fixed point of $ϕ \circ π$ is also a fixed point of $ϕ$ .

For that, the intended way is presumably to mirror the step from Ex4 to Ex5. The problem is that the coloring of the disk isn't drawn in a way that generalizes well. The nicer way to color it would be like this. One can see that these colors still work (i.e., a trichromatic triangle must contain the origin), and they're subsets of the previous colors, so the conditions of sides not touching colors still hold. This way of coloring is analogous to what we do in $d$ -dimension space.

Mathematically, one can describe these areas as follows:

The $d$ areas of the kind $C_{k} := {x \in R^{d} : \sum_{j = 1}^{d} x_{j} < 0 \land x_{j} \geq 0 \forall j \neq k}$
The area where all coordinates are non-negative, $C_{d + 1} := {x \in R^{d} : x_{j} \geq 0 \forall j}$

Given the $d$ -dimensional standard simplex $Δ$ and a continuous function $f : Δ \to Δ$ , the function $g : Δ \to R^{d}$ given by $g (x) = f (x) - x$ does have the property that each face of the simplex has one color it can't map into...

The first $d$ faces can be characterized by the condition that $x_{k} = 0$ . Then for a point $x$ in this face, we have $g (x)_{k} = f (x)_{k} - x_{k} = f (x)_{k} \geq 0$ , hence $g (x) \notin C_{k}$ .
The final face can be characterized by the condition that $\sum x_{j} = 1$ . Then for a point $x$ in this face, we have that $\sum g (x)_{j} = \sum f (x)_{j} - \sum x_{j} = \sum f (x)_{j} - 1 \leq 0$ , hence $g (x) \notin C_{d + 1}$ . (Unless $g (x) = O$ , in which case we're also happy.)

We still have to show that the image points of the $d + 1$ vertices of the simplex actually have all $d + 1$ colors. This is not necessarily true, but as above we can show that either it is true or one of them maps directly into the origin.

The $k$ -th vertex is the point $x$ with $x_{k} = 1$ and $x_{\neq k} = 0$ . We have $g (x)_{j} = f (x)_{j} - x_{j} = f (x)_{j} \geq 0$ for all $j \neq k$ , and $\sum g (x)_{j} = \sum f (x)_{j} - \sum x_{j} = \sum f (x)_{j} - 1 \leq 0$ . Thus, either $g (x) \in C_{k}$ or $g (x) = O$ .

And for the origin, we have $g (O)_{j} = f (O)_{j} - O_{j} = f (O)_{j} \geq 0$ , so $g (O) \in C_{d + 1}$

Now, either one of the first $d$ vertices maps directly into the origin, or we can construct a simplex with all $d + 1$ 'colors' for the map $g$ in $R^{d}$ . According to Ex9, this simplex has a $d + 1$ -chromatic component. It remains to show that the origin is always contained the span of such $d + 1$ points (tedius but pretty clear from the 2-d case), then we can again construct a sequence of points that converges toward the origin, by making the simplex progressively more granular. This gives us a point $x^{*}$ such that $g (x^{*}) = O = f (x^{*}) - x^{*}$ and hence $f (x^{*}) = x^{*}$ .

Ex 9

I'm weak with high-dimensional stuff, so I wanted to translate the statement into one about graphs. We characterize graphs by the following property:

Property P: every -clique in the graph has an equal number of extensions to $(j + 1)$ -cliques. (I.e., an equal number of nodes not in the clique that are connected to every node in the clique.)

(A simplex we translate into a graph has property P: every vertex has an equal number of edges it's a part of, every edge an equal number of faces it's a part of, and so on. That is, except for the vertices/edges at the... well, edges of the triangulation. Those have already made problems in Ex4.)

We now prove by induction that, given any $k \in N$ and a graph with property P where the largest cliques are $k$ -cliques, and any coloring $c : V \to {1, . . ., k}$ , the graph has an even number of $k$ -chromatic cliques.

Base case is $k = 2$ . The only such graph with property P is the cycle graph $C_{n}$ . Lemma follows from Ex. 1. (We need that $n \geq 3$ here, but that's fine.)

Inductive step: suppose the claim is true for some $k \in N$ and we have a graph where the largest cliques are $k + 1$ cliques and some coloring $c : V \to {1, . . ., k + 1}$ . We prove the step by constructing $c$ starting with the trivial coloring $c^{'}$ where $c^{'} \equiv 1$ . This coloring has no $k + 1$ -chromatic cliques, so in particular, the number of such cliques is even. We can transform $c^{'}$ into $c$ by repeatedly recoloring nodes, as in Ex4 -- and as in Ex4, the claim follows if we can prove that any step changes the number of $k + 1$ -chromatic cliques by an even number.

Let $x \in V$ , and suppose we change the color of $x$ from $n$ to $m$ . Recoloring $x$ can only change the $k + 1$ -chromatic-ness of cliques which contain $x$ . Let $ω$ be such a clique. Then $ω$ changes its $k + 1$ -chromatic-ness iff (a) precisely one of the nodes in $ω - {x}$ has color $n$ or $m$ , and (b) the remaining $k - 1$ colors of nodes in $ω - {x}$ are the set ${1, . . ., k + 1} - {n, m}$ . In other words, let $(V^{'}, E^{'})$ be the subgraph consisting of the neighbors of $x$ plus edges and let $c^{-}$ be the coloring obtained by $c$ if we merge colors $m$ and $n$ into one, then the number of cliques that change their $k + 1$ -chromaticness in $(V, E)$ is equal to the number of $k$ -chromatic cliques in $(V^{'}, E^{'})$ .

It now follows from the inductive assumption that the number of such cliques is even. We verify that $(V^{'}, E^{'})$ has property P: let $ρ$ be a $j$ -clique in $(V^{'}, E^{'})$ . Then, the claim follows from the fact that there is a one-to-one correspondence between $j + 1$ cliques extending $ρ$ in $(V^{'}, E^{'})$ and $j + 2$ cliques extending $ρ \cup {x}$ in $(V, E)$ . Furthermore, $(V^{'}, E^{'})$ has at most $k$ -large cliques since every node was connected to $x$ and thus lost one degree.

Given this, one can start with a triangulation where precisely one simplex is $k$ -chromatic (this is pretty straight-forward) and then use the Lemma to repeatedly recolor vertices without changing the number of $k$ -chromatic simplexes. Except, again, for the simplexes at the edges of the triangulation, but those should work similarly... I hope.

I've always meant to come back to these at some point.

Ex7

Compact subsets of the plane are bounded (cover such a set by an expanding sequence of open balls and apply compactness). This means we can view as a subset of not just $R^{2}$ but also the closed triangle $T \subset R^{2}$ , appropriately scaled. Let $π : T \to S$ be the projection (the exercise tells us that $π$ is continuous (compact subsets of Hausdorff spaces are closed) ). Then $f \circ π : T \to S$ is continuous and since $S \subseteq T$ , it has a fixed point $x^{*}$ according to Ex6. Since the image of $f \circ π$ is just $S$ , this fixed point must lie in $S$ , and since $f \circ π \equiv f$ on $S$ , it's the desired fixed point for $f$ .

I'll use the term "rainbox edge"/"rainbow triangle" instead of bi/tri-chromatic.

Some details are glossed over, but only when I am am confident I could fill them in. Sorry if you are reading this and want more detail.

Also, thanks again for these posts. They are really quite helpful. I mean, I'm kinda skeptical about usefulness towards alignment, but regardless I'm very glad you wrote them. I had heard legends of proofs of the Brouwer fixed point theorem from Sperner's lemma, but didn't realize how nice it would be - I prefer this to the usual topological proof.

1: I proved this theorem in like 3 related ways until one of the approaches managed to give traction on the generalizations

Suppose we change a node 'in the bulk', that is, a node surrounded by two nodes. Then if we change the color of this node, we'll either change the number of bichromatic edges by 0 (in the case where the nodes on either side have different colors) or 2 (where they have the same color). Thus we won't affect the parity, so we can willy nilly change the bulk.

Let's change the bulk to start with a blue on the leftmost, and green on the rightmost. Then we can by induction apply the lemma to this smaller segment. There are no extra bichromatic edges, so we are done.

Imagine subdividing the interval into 1/N size bits, with the endpoints colored green if the function is positive there, and blue if it's negative. If any are 0 we are already done, so let's suppose none are zero.

For each N, pick a rainbow edge, then take the sequence of green endpoints from picked edges. This must have a convergent subsequence by Bolzano-Wierestrass. Now take the corresponding blue endpoints from this sequence (connected by the chosen edges). We then also have a sequence of blue endpoints, which must also converge (to the same value) because the edge lengths go to 0. The value of the function there is equal to the limit of function values, because it's continuous - so therefore it must be both at least 0 and at most 0, and thus is equal to 0

3: Rewrite that's more in the 'spirit' of problem 5 and 6, but not the first I came up with.

Color each point by whether the function sends it somewhere more "right" or "left" (that is, greater or lesser) than it. First suppose that there's at least one point of each color. Then we can use the argument in the previous to get two converging sequences, one of "right" elements and one of "left" elements, that converge to the same value. When fed to the function, continuity means that we must be no bigger and no smaller than that value, and so must be equal.

If every point has the same color, then we send either 1 or 0 to something above/below itself, which is impossible because the function maps everything to [0,1].

It fails for (0,1) because you never need to plug in 0 or 1. For example, f(x) = 1/2 (1 - x) + 1/2 x is a counterexample - the fixed point is 1, which is outside (0,1). The function takes a point and then moves it halfway to 1. So everything is colored "right', which is why we fail.

You could more directly use the previous problem:

Apply IVT to e(x) = f(x) - x

but I prefer the other way.

4: Huh, this got progressively less messy as I tweaked my proof, and in the process bugs were fixed. And then made even simpler for problem 9. Simplicity is king, remember that.

What group should we use for the 2D case?

Each color will be a group element.

Color an edge by the 'missing' color. This is the same as comparing our edge to the sum of all three colors. That is, (R + G + B) - (difference of endpoints). This also tells us what 2 of the same color should be - it should be R + G + B. Having the same color should clearly give us 0, so we want R + G + B = 0. Then, the color of an edge is just the sum of endpoint colors (at least, we'll see that in a second when we show that -X = X).

Now, if we add the edges of a path, we should get the thing corresponding to the start and end endpoints. So we want e.g. G-B-G to be the same as G-G. That is, R + R = 0. Likewise, G + G = 0, B + B = 0, and G B R gives us that R + G = B. This is what we in the biz call the Klein four group, but you don't have to worry about that if you don't want to.

Any loop sums to 0. You can also think of this as counting each node twice. thus cancelling them.

Suppose we have a node in the "bulk" of the triangle, that is, one that's fully surrounded (like a hexagon). We'll show that we can change the color of the node without affecting the parity of the number of rainbow triangles. I'll call this the "bulk lemma".

WLOG imagine the center starts red and becomes blue, so our hexagon looks like (the Xs are arbitrary color values, not necessarily equal to other Xs)
X X
X R X
X X
and becomes
X X
X B X
X X

Now, how many rainbow triangles are at the beginning? Well, it's actually just the number of B-G aka red in the loop around the center - that is, the number of bordering edges that are missing a red. Likewise, at the end it's the number of R-B aka blue edges in the loop. But neither of these numbers depend on the center! So as long as the number of red and blue edges in the loop has the same parity, we can freely change the center node.

Now, to prove the bulk lemma, we'll show that parity differences must be 0 for any loop. This is kinda like saying that not only do we know that the sum/center of mass of the vectors are 0, but we also know something about the angles (don't take it too literally though).

Red is like the vector 1,0, Green is like 0,1, and Blue is like 1,1 (addition is mod 2). When we add in a loop, the total sum is 0,0. Note that Blue's don't screw up parity differences between Red and Green, cuz they add 1 to both.

So the difference/sum of the two coordinates is equal to the parity difference of reds with greens, because the blues don't affect it. Since the vector is 0,0, it has sum 0, which is 0. So we're good.

We could've just as easily swapped our basis to use a different clor as the all ones, and so we get that all parity differences are 0.

Since for hexagons the parity of the number of rainbow triangles changes according to the parity difference of a loop, and since those differences are always 0, we can freely change the center node.

Note that it's quite important that we have a loop that doesn't go through the center - as you can see by looking at the following half-hexagon pattern from about the middle of the left side of the image for the problem:

R
B B
B G

Changing the center B to a G increases the number of rainbow triangles by 1.

Alright, now for the theorem. We can change the "bulk" nodes in such a way that we can do an induction argument. That is, we can change them so that the left side of the inner triangle has no green, the right side of the inner triangle has no blue, and the bottom side of the inner triangle has no red. Now there are an odd number of rainbow triangles inside the inner triangle. Because of our coloring of the sides, the only possible way to have extra rainbow triangles are the "outtermost" ones near an inner corner, e.g.

R
X X
O R O
Y B G Z
B Y O Z G

Where the X, Y, Z's mark the two extra nodes of each of the 6 triangles being referenced here, while the O's mark extraneous nodes that don't matter.

Now, due to our coloring choice, we see that to get extra rainbow triangles two of the X,Y,Z nodes with the same letter should have different colors. But, this gives us another rainbow triangle, using that as the same side. This is because we picked the corners of our inner triangle to match those of the overall big one.

Therefore, we only have an even number of extra rainbow triangles. So we have an odd number total.

Let's color points according to where the function sends them. We know the vertices go to R G B as expected. We can subdivide the triangle, giving us something that will satisfy the conditions of Sperner's lemma no matter how finely we subdivide. For each subdivision, there'll be a rainbow triangle, giving us a sequence of rainbow triangles.

If we then take the sequence of the red vertex of this sequence of rainbow triangles, there'll be a convergent subsequence of them. We can then take the associated blue and green vertices, to get three convergent subsequences, and the limiting values of the function must be equal. This value, however, must be a limit point of the green, blue, and red subsets of the disk. The only such point is the center.

Suppose every point of the triangle moves. Then it must be moving 'closer to' some side. More precisely: Take a point x. Look at f(x). Draw the ray from x to f(x), and at some point it'll hit the boundary of the triangle. It will either hit a side, or hit a vertex (aka hit two sides). For the latter case, we can just fix at the outset some choice of colors for the vertices that agrees with the sides. For example, suppose we color the sides R G B, and the RG vertex R, the GB vertex G, and the BR vertex B. Think of this coloring as being on the codomain/second triangle, and then giving rise to a coloring on the inputs. The vertices must move towards the opposing face.

Now, no point on an edge in the domain can be colored the same way the point in the codomain is, as that would mean you moved off the triangle.

This lets us subdivide the triangle successively. We can then get a sequence of red, green, and blue points whose outputs converge to the same value, which then means we must not move at all.

If you aren't convinced of that last fact: you can express "move closer to" via linear functions (just negative dot product of (f(x) - x) onto the vector from the center to a vertex), and thereby get a generalization of the fact that f(x_i) > 0 for all i implies that f(limit of x_i) >= 0. Alternatively you can directly use problem 5 like in my second proof of problem 3.

7: Sidenote: I think the reason why the projection is well defined is:

You have a convex optimization problem that has a unique solution. More intuitively, you can just do classical geometry:

Since S is closed, you know that there is at least one closest point. (otherwise you can take an infimum of distances, and then take a sequence of progressively closer points, which must converge to a point closer than all points in S since distance is continuous, but since it's closed you must get a point actually in the set). (alternatively just use the extreme value theorem).

If two points A, B in S are both closest to P then they lie on a sphere around P. Then the interior of the spherical sector APB must not be in S because all of it is closer to P. But the chord AB must be contained in S by convexity, which is a contradiction.

The closest is continuous: Suppose we have some P. Let's say that X is the closest point in S. The set S must lie to one side of the perpendicular hyperplane to PX (based at X) because otherwise there would be a point that's closer to P (because the line from a point on the wrong side to X would intersect the inside of the sphere of radius PX centered at P, and all points inside the line are in S).

Suppose we have some other point Q, with closest point Y. If Q is on the line PX, then Y=X. So we can assume Q isn't on PX. Now, hyperplane cuts need to 'agree'. Let's say that the perpendicular hyperplane that PX gives us is H. There is a closest point Q' on H to Q, given by projecting.

If the closest point in S to Q is 'further away' from X than Q' is then the hyperplane cut corresponding to QY will exclude X.
Precisely: Y must lie between the two hyperplanes perpendicular to XQ' that contain X and that contain Q' respectively. That is, it lies in a 'channel'. XQ' is at most as long as PQ, so it's a channel at most as wide as PQ is (call it delta). We then have a plane geometry problem on the plane XYQ'. Our 'agreement' condition may as well use dot products of projected vectors on this plane (that is, Q'Y and Q'X instead of QY and QX). For the cuts to agree, the perpendicular to YQ' at Y must intersect XQ' between the two points, say at Z. Then Q'YZ is a right triangle with hypotenuse Q'Z, so YZ has length less than Q'Z. Finally XY has distance at most XZ + XY <= XZ + ZQ' = XQ' <= PQ <= delta

Thus for any epsilon, we can choose some delta < epsilon to ensure that XY is within epsilon whenever PQ is within delta.

Okay, now for the actual problem.

The intuition: Let's imagine picking a center point of our set S, and then classifying the directions like we would on the triangle.

Here's what we actually do, which is close enough: find a triangle that is a superset of the set S (we can do this because it's compact and so bounded). Then we can compose with projection to get a continuous function from the triangle to (the subset S of) itself. Since we know this has a fixed point, yet moves every point that is outside S (but still in the triangle), we know it has a fixed point in S.

Reflecting: Imagine someone gave you the colors of a path like in 1. To find a bichromatic edge, you might have to look at all (but one) edge first! Likewise, with the intermediate value theorem/1D Brouwer, you'd have to check 'infinitely' many points to pin down the intermediate value/fixed point (or to get epsilon = 1/N accuracy, you'd have to check about N edges). 2D Sperner requires you to check all but one tiny triangle as well - as we can for example force it to be any of the triangles. Etc.

For functions: let's look at it in the e(x) = f(x) - x formulation, where fixed points are roots and the problem forces -x <= e(x) <= 1 - x. The idea is to give a choice between two roots, force a commitment to one of them by destroying the other, recreate it, and then destroy the committed one.

Let's force a commitment by 'stomping'. We start as a 'hump' that's 0 at both x=0,1. Then, we lift our left leg up. We can do this easily by linear interpolation. Then, we turn our hump into a valley (what a poor camel). For an instant, half the points will be fixed points - but because this will only be true for an instant, our adversary won't be able to take advantage of this to jump to the other root. Then, we pull our right 'arm' down, thus leaving our adversary stranded.

That is, for 0 <= t <= 1/3, let
e_t(0) = 3/2 t -- goes from 0 to 1/2. T
e_t(1/2) = 1/2
e_t(1) = 0.

In between, we'll do linear interpolation.
The left leg stops being on the ground at t=0. So any continuous choice of root has to commit to choosing x=1 for this period.

Now, we'll turn the hump into a valley:
For 1/3 <= t <= 2/3:
e_t(0) = 1/2
e_t(1/2) = 3 (1/2 - t) -- goes from 1/2 to -1/2
e_t(1) = 0

and we'll interpolate in x the same way as before. The continuous choice of root has to keep its commitment - it can't use the instant where [1/2,1] are all roots to jump to the left, as it is only an instant.

Now, we'll pull our right arm down:
For 2/3 <= t <= 1:
e_t(0) = 1/2
e_t(1/2) = -1/2
e_t(1) = 1 - 3/2 t -- goes from 0 to -1/2

and we'll again interpolate in x.
The right arm stops being at the 'ground' at t=2/3, so now the choice of root is screwed.

To make our fixed point function: observe that the function is always bounded between u(x) = 1 - x (which is always at least 1/2 for x in [0, 1/2]) and l(x) = x - 1 (which is always at most -1/2 for x in [1/2, 1]). So f_t(x) = e_t(x) + x is a legitimate function from the interval [0,1] to itself.

Suppose each face of an nD simplex that's subdivided like in the 2D case is known to only use all but 1 color, going through the sequence. e.g. for n=3 there's a ABC face, a BCD face, a ACD face, and a BCD face. We should have n+1 colors, as the simplex has n+1 vertices.

Now, what will be the analog of paths, what group do we use, and what's our version of a loop? Well, I claim we should be using faces. We can put faces together to make a closed volume. Another way to look at the sum over a loop of edges is to notice that we double count every node when we add the edges together. Likewise we'll double count each (n-2)D face ('edge' in the n=3 case) of the volume when we add the (n-1)D faces together.

We want this to be 0, so our group elements that we assign to faces should satisfy g + g = 0. For the tiniest face, we have n nodes in a (n-1)D face, and there so we can just label by the missing color/label by sum of nodes. The group is (Z/2Z)^n.

Now, if we take some tiny faces, and put them together in a way that closes a volume, then we will indeed have double counted every node and thus get 0 in our sum.

Onto the bulk lemma. Let's show that if we change a node 'in the bulk', the parity of the rainbow simplices is unchanged. We're looking at a 'honeycomb' like hexagonal like thing around a center. WLOG let's suppose we change the center color from R to G. The number of rainbow simplices at the start is the number of R faces surrounding the center; and at the end it's the number of G faces. Therefore, we'll want to show the parity difference between the number of R faces and G faces is 0.

Imagine an enclosed volume. We can think of our group this way: assign the first n colors to one hot nD basis vectors that have a 1 in the ith coordinate, while the (n+1)th color goes to the all ones vector (and addition is mod 2). Pick the basis so that R and G are the first two colors. The parity difference between the number of R faces and the number of G faces is the sum of the first two coordinates of the total (group) sum - that is, the group sum's first two coordinates won't get mucked up by adding the all ones vector, because that changes the parity of every other color by 1; and any other color besides R or G just doesn't change those two coordinates.
The group sum must be the 0 vector; so the sum of the first two coordinates must be 0.

No matter what two colors we want, we can choose a basis where those are the first two. Therefore the parity difference between the number of any two colors in a face sum is unchanged when we add a closed volume.

Thus, the parity of rainbow nD simplices is unchanged when we change the color of a node in the bulk.

Now, we can proceed like in problem 4, by coloring the overall faces of the inner simplex like that of the outer one, and use induction to say that there are an odd number of rainbow simplices in there. Due to how the inner bottom face is missing the same color that the outer bottom is, and etc., the only possible simplices to worry about are the (n+1) that correspond to each corner vertex, or the paired ones that share a tiny face with those. But since the corner vertices of the inner simplex are the same as the outer, we'll only pick up a rainbow simplex if we pick up a paired one. Thus we get an even number of extra ones, and so the total parity is still odd

10:

First, the IVT analogue (2 and 5):

We can color the n-ball like we did the ndisk. We can do this by taking a coloring of the (n-1)ball, and then 'inflating' it, and then adding a nth color below it, that takes up only a volume and outside of the ball (without taking up an internal face, like how blue doesn't in the image for 5). In the image for 5, you can imagine a green point, that inflates to a green line and is then connected to a red line (where the intersection point is green), which inflates to the two sectors of the image for 5 and is then connected to the blue sector. You can repeat this process.

Then given a continuous function from a closed simplex to that ball, that sends each ith face to non i-colored points, we can then subdivide the simplex, take sequences of rainbow triangles and thus points, yadayada it's the same argument as before.

Then, the version of 3 and 6:

Suppose we have a continuous function from the closed nD simplex to itself. If every point 'moves' then it must be moving closer to some 'face', which we can determine by casting a ray from x to f(x) and seeing which side it hits, and then coloring appropriately. The points on each face cannot move outside the triangle, and so must move towards any face but itself - and so that face's colors in the domain must not have the color we gave to it in the codomain (aka the face's colors in the domain must not be the group element of "missing color" we gave to it). Vertices must move towards the opposing face, which also works.

We then have a simplex satisfying the conditions of Sperner's lemma, so we can get the sequences wewant

Then, the version of 7:

Just take a bounding simplex of the compact subset, then projection is a retraction map (continuous map that sends to a subspace and fixes the subspace) because it's a convex subset, and so if we compose with our continous function f then we'll get a function from the triangle to itself, which must have a fixed point, which must then be in the subset.

11:

First, just thinking about continuous Hausdorff limit. Let's say we had f(x) = [-1,1] for x in [0,1], that is, a graph that's a rectangle. To get a limit, we could try sine waves of increasing frequency. Since they are in that rectangle, d(a,B) is 0; while max_b d(b,A) depends on how well the sine wave fills the box. If we fill the box well enough, that max will be small (cuz it's 2D distance - in general, product distance) - so we just need to fill the box.

I believe the statement also implicitly assumes that the graph of f is a (nonempty) compact set - as otherwise you couldn't use the Hausdorff distance when stating that it's a continuous Hausdorff limit.

A continuous Hausdorff limit f: T -> 2^T where T is a compact convex subset will be given by a sequence of continuous functions f_n: T -> T. Each function in this sequence has a fixed point by the Brouwer fixed point theorem - and the question is whether f does too.

Let B be the graph of f, and A_n the graph of f_n. Note that B is compact (by assumption), and A_n is too (by the extreme value theorem and compactness of T).

We know sup_{x in A_n} d((x, f_n(x)), B) converges to 0 as n goes to infinity. If we take the sequence (x_n, f_n(x_n)) where x_n is a fixed point of f_n, then d((x_n, x_n), B) = d((x_n, f_n(x_n)), B) <= the sup -> 0. Since B is compact, we know that the sequence is bounded. We can then take a convergent subsequence, giving us some limit I'll call (x', x'). This limit must be of distance 0 from B, but then it is in B since B is closed.

But if (x',x') is in B, then x' is in f(x'), and we are done.

12: TODO. Current progress.

First let's note that S \times T is compact, and so if the graph of f is closed then the graph is also compact.
Note also that for any x, f(x) is closed, and thus also compact.

Let's do the given example. In my head, I'm thinking of approximating an infinitely steep ramp by making increasing faster ramps. If instead we tried to make x <= 1/2 go to {0} while x > 1/2 goes to {1}, we'd to be closed. If instead x = 1/2 goes to {0,1} then we'd fail convexity. If we try f(x) = {1} if x is rational else {0}, then we fail to be closed.

Suppose f only assigned one element to each input. We'd like to show that the function assigning each x to the only element of f(x) is continuous.

Consider the projection to the y-axis. This is a continuous function, so the preimage of a closed set of y-values is a closed set of the graph. Then the projection to the x-axis must also be closed, because there's only one element in f(x), and so if a sequence of points converges in the graph they must have their x values converge. Thus the function assigning each x to the only element of f(x) is continuous, as the preimage of a closed set under it is closed.

More generally: Any closed subset of the graph that passes the vertical line test corresponds to a continuous function. Since each vertical slice of the graph is convex, we know that we must have an entire line segment anywhere the vertical line test fails.

Suppose now that there's exactly one point c where f(c) has more than one element. The left and right limits of f(x) as x goes to this point must be contained in f(c). If we take the maximum and the minimum height points of f(c), then f(c) is just a line segment. We can make our limit with a "heartbeat" pulse that follows the curve of f(x) to the left of f(c), then near it dips down to the minimum, goes back up to the maximum, and then rejoins the curve. That is, for each N, we'll follow f until f(c - 1/2N), then dip down to min_height f(c) at c - 1/4N, then go up to max_height f(c) at c + 1/4N, then fall back down to f at f(c + 1/2N). We'll do our movements via linear interpolation. We can always choose big enough N such that f(c - 1/2N) is always 'almost' (at most epsilon from not being) above min f(c), because we know the limiting value must be. Likewise, the right side will always be 'almost' above the max for large enough N. We can do this because the limiting values are contained in f(c), and we can pick N big enough so that the function is within epsilon of the limiting values. Thus the 'directional' words used are accurate.

We now need to check that this converges in Hausdorff distance. We'll need to check that both of the sups converge. First let's do sup_b d(b,A_n). We don't have to worry about the b's that are outside of our little pulse interval, because those are distance 0 away from A_n. For values (x,y) that are to the left of c, we know that (c-1/2N, f(c - 1/2N)) is in A_n. If we choose N small enough, we can ensure that f(c-1/2N) is within epsilon of our value f(x). Since we also know that the x values are close enough, we have a good bound. Likewise this works for the values that are to the right of c. For the values at c, we know that each is at most 1/4N away from some point on our ramp at the same height. Thus we have sufficient bounds on each d(b,A_n).

For sup_{a in A_n} d(a,B): if a is outside our pulse interval, then we are fine. For big enough N, we know that f(c) has y values at most epsilon away from every y value between the smallest and largest value of f in our pulse region. We thus know that every point a on our pulse graph is at most 1/2N away from an equal height point at c. This gives us our other bound.

Therefore, when there's exactly one 'thick' point, we can stil find a limit.

Clearly, this generalizes to finitely many thick points, by just stitching functions together. Now we need to be able to deal with countably infinitely many thick points (think of putting an interval at every point 1/2^n, including 0) and 'thick widths' like a square. Let's try the thick widths.

We can try 'bouncing' a line up and down through a region, progressively filling it. To do this, we might try to take the Upper curve U(x) = max_height f(x) and the Lower curve L(x) = min_height f(x). These always exist, by compactness of f(x). Note that these curves might not be continuous. For example, if there's a straight line rise, then U has a jump discontinuity that at the discontinuity returns the higher point.

Now, for every N, let's subdivide the interval into N parts, and then linearly bounce up and down between the values of U and L. Note that we can actually cross U and L sometimes, while en route to a U or L value.

There's however a problem when we try our limits. e.g. for the sup over b, what if our b value has a taller interval than the U and L values near it?

So instead, let's bounce our line like our heartbeat from earlier: in an inteval [a,b], we can try bouncing a line from L(a) to the tallest point in the whole interval, and then down to the lowest point, and then back to U(b). If instead the tallest comes after the lowest, we can bounce ...

13:

Just look at 11 and 12.

I'm just working my way through these problems in sequence.

1 is not particularly difficult to solve

Let's imagine the base case: B-G. Obviously, there is 1 biochromatic edge. Adding either B or G to a biochromatic edge will turn it into B-B-G or B-G-G respectively, which means there is still 1 bichromatic edge.
If you add B to a B-B or G to a G-G it turns into B-B-B or G-G-G, which does not add or destroy any bichromatic edges.
The final case is adding G to B-B or B to G-G, which makes either B-G-B or G-B-G, adding two bichromatic edges. Since adding two to an odd number results in an odd number, and we begin with 1 bichromatic edge, we always have an odd number of edges.

For a formal proof, we'd have to prove the unspoken assumption that we can make any finite linear path made up of Blue/Green nodes where the start is a Blue node and the end is a Green node, by adding Blue/Green nodes in between a B-G path.

The proof is as follows: Besides the start and end nodes, every node has two connections. Thus, we can remove a node and connect its two adjacent nodes to each other in its place. Removing a node this way does not make it no longer a qualifying path under our definitions, and the removal of a node can be undone by adding it back in between the two nodes. Thus, since we can remove all the nodes until we're left with a single B-G path, we can add them back until we've reached the original path, while still ensuring that there is an odd number of bichromatic edges.

76

Topological Fixed Point Exercises

76

Ω 23

76

Ω 23

76

Ω 23