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 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 just tried to fix all the things in your comment. You’re right, weird stuff was happening :-)
Thank you!