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:
Here's a more conceptual framing:
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:
On my approach:
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:
#8:
Found a nice proof for Sperner's lemma (#9):
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:
Awesome! I was hoping that there would be a way to do this!
Some preliminary thoughts on q9:
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 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:
My solution for #3:
Define g:[0,1]→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∈[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)→(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.
Yeah, I did the same thing :)
I'm late, but I'm quite proud of this proof for #4:
Here's the rough idea for 5 (not a full-proof)
Yeah, you're right. That breaks the proof. I don't know how to deal with it yet.
Here's a solution to 4:
Strategies that I've found helpful:
Specific solutions (or suggestive handwaving):
Problem 1:
Problem 2:
Problem 3:
#8 actually comes up in physics:
Does this work for #7? (and question) (Spoilers for #6):
An attempt at problem #1; seems like there must be a shorter proof.
:::
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.
Pointers welcome!
Here's a messy way that at least doesn't need too much exhaustive search:
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.
I was able to get at least (I think) close to proving 2 using Sperner's Lemma as follows:
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?
Here is my attempt, based on Hoagy's proof.
Let n≥1 be an integer. We are given that f(0/n)=f(0)≤0 and f(n/n)=f(1)≥0. Now consider the points 0/n,1/n,…,(n−1)/n,n/n in the interval [0,1]. By 1-D Sperner's lemma, there are an odd number of j∈{0,…,n} such that f(j/n)≥0 and f((j−1)/n)≤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 jn.
Now consider the sequence (jn/n)∞n=1. Since this sequence takes values in [0,1], it is bounded, and by the Bolzano–Weierstrass theorem there must be some subsequence (kn/n)∞n=1 that converges to some number x∈[0,1].
Consider the sequences (f((kn−1)/n))∞n=1 and (f(kn/n))∞n=1. We have f((kn−1)/n)≤0≤f(kn/n) for each n≥1. By the limit laws, (kn−1)/n→x as n→∞. Since f is continuous, we have f((kn−1)/n)→f(x) and f(kn/n)→f(x) as n→∞. Thus f(x)≤0 and f(x)≥0, showing that f(x)=0, as desired.
Ex 1
Ex 2
Ex 3
On your Ex. 2:
Ex 5 (fixed version)
Ex 6
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∈[0,1]|f(y)≥0} . If f(x)>0 then x≠0and, 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)≥0 and g(1)≤0 by exercise 2, there should be a point where g(x) = 0.
#8.
Consider the family of functions: ft(x)=min(max(x−t+0.5,0),1)
For t < 0.5, the only fixed point is of ft 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.
#4
Follows from 9
#5
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 Dno itself has a fixed point, then that any compact convex subset of Rns homeomorphic to a ball.
Suppose that f:Dn→Dnas no fixed point, n>1 (case n=1 was proved in exercise 3). Then I can build a retraction from Dnnto its boundary Sn−1
send x to the first intersection of the ray (f(x), x) with Sn−1 Let us prove that such a rectraction cannot exist. Suppose that such a rectraction g exists. Denote i:Sn−1→Dnthe inclusion map. Then g∘i=idnd the induced homology group homorphism g∗∘i∗ust also be identity: Hn−1(Sn−1)→i∗Hn−1(Dn)→g∗Hn−1(Sn−1)
But this is impossible because Hn−1(Sn−1)=Z and Hn−1(Dn)=0
Now let us prove that any compact convex subset X of Rns 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 Dkf radius d side this simplex and build a homeomorphism between X and Dk. 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≠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)≤R It follows that f and its inverse f−1(x)=x∗r(x)/d are continuous in zero: ∀ϵ>0 if |x|<R/d∗ϵ |f(x)|<ϵ ∀ϵ>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 Dk 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→2S is a Kakutani function. We already know that any compact convex subset of Rns homeomorphic to a simplex. Denote g:T→She homeomorphism between a simplex T and S.
Denote yk1,…,ykt the k-th barithentric subdivision of T. For each yki, choose an element hki∈h(g(yki))
Define fk(x) ∑n+1i=1pki(g−1(x))hki where pki are the baricentric coordinates of point g−1(x)n its subdivision simplex. Function fks continuous, fk(g(yki))=hki and, since S is convex, the image offk lies in S.
By the Brouwer fixed point theorem, fkas a fixed point. Since S is compact, from the infinite sequence of fixed points of fke can choose a convergent subsequence.
Suppose xk→x∗s this subsequence, g−1(xk) lies in the simplex yk1,…,ykn+1and has baricentric coordinates pk1,…,pkn+1. Then g−1(xk)=∑pkiyki and fk(xk)=∑pkihkiso
g−1(∑pkihki)=∑pkiyki (1).
Since simplices go down in diameter, g(yki)→x∗as xk→x∗ Each pki∈[0,1]s a bounded sequence, so we can, sequentially, choose a convergent subsequence out of each of them, so we can assume that pki→p∗i Similarly, we can choose a convergent subsequence out of hki so we assume hki→h∗i The sequence (g(yki),hki) 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 ∑pki=1 for every k, ∑p∗i=1.ince the image is convex, ∑p∗ih∗ilso 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(∑p∗ih∗i)=∑p∗ig−1(x∗). Hence, ∑p∗ih∗i=x∗ So, x∗ is the fixed point of h.
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.
2:
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.
5:
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.
6:
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.
8:
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.
9:
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.
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 S 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 fn 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 fn to S without wandering off too far, and voilà.
Proof roadmap:
(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⊆X:=[0,1]d and T⊆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∈N+.
(2) By cutting each interval into n pieces, i.e., [0,1n],[1n,2n],...[n−1n,1], we obtain nd small cubes in X of the form
[j1n,j1+1n]×⋯×[jnn,jn+1n]
where j1,...,jn∈{0,...,n−1}. Enumerate these cubes as Cubes(X):={C1,...,Cnd}. An analogous construction for Y yields Cubes(Y):={D1,...,Dnm}.
Given any set Q⊆Y, we define the operator Expand to 'expand' Y to all the cubes that it touches, i.e.,
Expand(Q):={D∈Cubes(Y)|D∩Q≠∅}
(3) We do most work via paths. This requires a bunch of Lemmas.
Lemma 1. For any connected set C⊆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∈C not entirely contained in U or V. Then, U∩f(x) and V∩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×U)∩Gf and π1((S×U)∩Gf) (where Gf 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∩f−1(V))⊔(C∩f−1(U)) is a separation of C, implying that (because C is connected), one of them is the empty set. Since U,V⊆f(C), this implies that U=∅ or V=∅.
This is only needed to prove Lemma 2.
Lemma 2. For any connected set C⊆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∈D⊆Z and p′∈D′⊆Z, we can construct a path from p to p′ via
p→center(D)→center(D′)→p′.
Lemma 3. Given k∈N+ and any path-connected space Z, all functions from [0,1]k to Z are homotopic.
Proof. Let ϕ:[0,1]k→Z. Define a homotopy Φ:[0,1]×[0,1]k→Z by the rule Φ(t,x1,...,xk)=Φ((1−t)x1,...,(1−t)xk). 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→Z are homotopic to each other.
(4) Let ϵ∈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⊂S be connected. We define two operators on A. The first is the set of points in Y that wish for fn to hit on points near it. We set
Targets(A):={center(D)|∃x∈B(A,ϵ):f(x)∩D≠∅}
where B(A,ϵ)={x∈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 fn:X→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∈Cubes(X) that intersect S.
A vertex v is defined to be a point v∈X of the form
v=(j1n,j2n,...,jnn)
for some j1,...,jn∈N. The set Area(v) may be empty if v is too far outside S, in which case we leave fn undefined on v. If it is not empty, choose y∈Area(v) arbitrarily and set fn(v):=y.
We now turn to edges. However, we only consider 'horizontal' edges, that is, subspaces e⊂X of the form
e={(a,j2n,...,jnn)|a∈(j1n,j1+1n)}
for some j1,...,jn∈N. Let v and w be the two vertices of e. If fn 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 fn hits all points in the target set.
We know from Lemma 3 that there is a path p:[0,1]→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→Area(e). But we can do even better and construct a path p∗:e→Area(e) that starts at fn(v), ends at fn(w), and hits all points in Targets(e) on the way. (All trivial since Area(e) is path-connected.) Now we simply set fn(x)=p∗(x)∀x∈e.
We next consider all 'horizontal-vertical' faces, that is, all sets q⊂X of the form
q={(a,b,j3n,...,jnn)|a∈(j1n,j1+1n),b∈(j2n,j2+1n)}
for some j1,...,jn∈N. Let e and e′ be the two horizontal edges of q. If fn is undefined on either, we leave it undefined on q. If not, we have two paths p:[0,1]→Area(q) and p′:[0,1]→Area(q) which implement fn on e and e′, respectively. Using Lemma 3, we obtain a homotopy F:[0,1]×[0,1]→Area(q) that continuously deforms p into p′. Since our face q is homeomorphic to [0,1]×[0,1], it's easy to transform F into a function F∗:q→Area(q). Now we simply set fn(x)=F∗(x)∀x∈q.
Now we do the same for 3-dimensional subspaces r⊂X of the form
r={(a,b,c,j4n,...,jnn)|a∈(j1n,j1+1n),b∈(j2n,j2+1n),c∈(j3n,j3+1n)}
where fn 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 fn on both, we can apply a construction analogous to the above to define fn on the k-dimensional subspace. Eventually, we define fn 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∈Cubes(X)). Importantly, this defines fn on any cube C∈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 fn on any edge, face, and so on, of C.) Thus, we end up having defined fn on some subspace of X that includes all cubes that intersect S.
The advantage of this construction is that, for any C∈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 fn 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 fn on a subset of X that contains S, we take a projection π:Y→T, and define ϕn:S→T by the rule ϕn(x)=π(fn(x)). It remains to show that our construction is such that the Hausdorff distance between f and fn converges to 0 as n→∞, then the distance between f and ϕn converges to 0 as well. (To see this, note that, if fn(x) is within δ of f(x) (which lies in S), then π can move it by at most δ, which means that π(fn(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∈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 ϵ∈R+ fixed, and show that n eventually grows large enough for that ϵ to suffice.
For every point x∈S, there exists some δ∈R+ such that B(x,ϵ) contains some δ-ball entirely contained in S. Define a function γ:S→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 (xn)n∈N of points in S, assuming that (γ(xn))n∈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 fn. This consists of showing two parts:
Both are now easy:
Ex13
Follows from Ex11 and Ex12 :-)
Ex11
(I assume the graph of f is compact; otherwise, the Hausdorff distance isn't defined, and there seem to be counter-examples to the claim of the exercise.)
Since each fn is a continuous function from T to itself, it has a fixed point xn by Ex10. Then (xn)n∈N is a sequence of points in a compact space and thus has a limit point x∗.
Let Gf be the graph of f. Assume for a contradiction that x∗∉f(x∗). Then, (x∗,x∗)∉Gf. Since Gf is a compact subspace of the Hausdorff space Rn, it is also closed. Let O⊊T be an open set around (x∗,x∗) disjoint from Gf. Then, we find an ϵ∈R+ such that B((x∗,x∗),ϵ)⊆O. (This uses that T is convex, otherwise the ball would exist in Rn but could fall out of T and hence O.)
Choose N⊆N infinite such that (xn)n∈N is entirely contained in B(x∗,ϵ2). Note that (xn,xn)∈Gfn by construction. Write D for the Hausdorff distance, then D(Gf,Gfn)≥d(Gf,(xn,xn))≥ϵ2∀n∈N. This contradicts the fact that (D(Gf,Gfn))n∈N converges to ⟶0, hence x∗∈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⊊Rd compact and convex and a continuous function ϕ on S, we can scale S to be a subset of Δd, take the continuous projection π:Δd→S, and ϕ∘π gives us a function from Δd to itself. Now, a fixed point of ϕ∘π 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:
Given the d-dimensional standard simplex Δ and a continuous function f:Δ→Δ, the function g:Δ→Rd 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...
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 xk=1 and x≠k=0. We have g(x)j=f(x)j−xj=f(x)j≥0 for all j≠k, and ∑g(x)j=∑f(x)j−∑xj=∑f(x)j−1≤0. Thus, either g(x)∈Ck or g(x)=O.
And for the origin, we have g(O)j=f(O)j−Oj=f(O)j≥0, so g(O)∈Cd+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 Rd. 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 j-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∈N and a graph with property P where the largest cliques are k-cliques, and any coloring c:V→{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 Cn. Lemma follows from Ex. 1. (We need that n≥3 here, but that's fine.)
Inductive step: suppose the claim is true for some k∈N and we have a graph where the largest cliques are k+1 cliques and some coloring c:V→{1,...,k+1}. We prove the step by constructing c starting with the trivial coloring c′ where c′≡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∈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 ρ∪{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 S as a subset of not just R2 but also the closed triangle T⊂R2, appropriately scaled. Let π:T→S be the projection (the exercise tells us that π is continuous (compact subsets of Hausdorff spaces are closed) ). Then f∘π:T→S is continuous and since S⊆T, it has a fixed point x∗ according to Ex6. Since the image of f∘π is just S, this fixed point must lie in S, and since f∘π≡f on S, it's the desired fixed point for f.
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.
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 theorem
3. (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.
11. Given two nonempty compact subsets A,B⊆Rn, the Hausdorff distance between them is the supremum
max{supa∈Ad(a,B),supb∈Bd(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→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.