Mentioned in

Topological Fixed Point Exercises

7nshepperd

2lbThingrb

2Charlie Steiner

7Hoagy

3Chris_Leong

5Adele Lopez

4lbThingrb

2Adele Lopez

5Jessica Taylor

5Issa Rice

3Charlie Steiner

3Chris_Leong

5Gurkenglas

5Paul Crowley

4Chris_Leong

4Rafael Harth

4Chris_Leong

4gjm

4Chris_Leong

3TheWakalix

3Rafael Harth

3Charlie Steiner

3Charlie Steiner

3Chris_Leong

3Hoagy

3Chris_Leong

3Chris_Leong

3David Manheim

4Adele Lopez

4Hoagy

3David Manheim

6Hoagy

3Issa Rice

4Chris_Leong

3Hoagy

2Czynski

4Issa Rice

2Rafael Harth

2Gram Stone

4Gurkenglas

New Comment

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.

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

Cleanest solution I can find for #8:

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

We take our close*d convex set tha*t has the bounded function . We take a triangle that covers so that any point in is also in .

Now we define a new function such that where is the function that maps to the nearest point in .

By #6 we know that has a fixed point, since is continuous. We know that the fixed point of cannot lie outside because the range of is . This means has a fixed point within and since for , , 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.

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

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 n edges as shown. Color each vertex blue or green such that the leftmost vertex is blue and the rightmost vertex is green. Show that an odd number of the edges will be bichromatic.2.(Intermediate value theorem) The Bolzano-Weierstrass theorem states that any bounded sequence in Rn has a convergent subsequence. The intermediate value theorem states that if you have a continuous function f:[0,1]→R such that f(0)≤0 and f(1)≥0, then there exists an x∈[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 theorem3.(1-D Brouwer fixed point theorem) Show that any continuous function f:[0,1]→[0,1] has a fixed point (i.e. a point x∈[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 n2 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 R2 to itself has a fixed point. (You may use the fact that given any closed convex subset S of Rn, the function from Rn 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∈[0,1], ft:[0,1]→[0,1], and the function t↦ft 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 ft 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 Rn to itself has a fixed point.

max{supa∈Ad(a,B),supb∈Bd(b,A)}11.Given two nonempty compact subsets A,B⊆Rn, the Hausdorff distance between them is the supremumover all points in either subset of the distance from that point to the other subset. We call a set valued function f:S→2T a continuous Hausdorff limit if there is a sequence {fn} of continuous functions from S to T whose graphs, {(x,y)∣y=fn(x)}⊆S×T, converge to the graph of f, {(x,y)∣f(x)∋y}⊆S×T, in Hausdorff distance. Show that every continuous Hausdorff limit f:T→2T from a compact convex subset of Rn to itself has a fixed point (a point x such that x∈f(x)).

12.Let S and T be nonempty compact convex subsets of Rn. We say that a set valued function, f:S→2T is a Kakutani function if the graph of f, {(x,y)∣f(x)∋y}⊆S×T, is closed, and f(x) is convex and nonempty for all x∈S. For example, we could take S and T to be the interval [0,1], and we could have f:S→2T send each x<12 to {0}, map x=12 to the whole interval [0,1], and map x>12 to {1}. Show that every Kakutani function is a continuous Hausdorff limit. (Hint: Start with the case where S is a unit cube. Construct fn 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⊆Rn 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.