Topological Fixed Point Exercises

Scott Garrabrant; SamEisenstat

Topological Fixed Point Exercises — AI Alignment Forum

Fixed Points

23 Topological Fixed Point Exercises

by Scott Garrabrant, SamEisenstat

17th Nov 2018

3 min read

23

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

1. (1-D Sperner's lemma) Consider a path built out of edges as shown. Color each vertex blue or green such that the leftmost vertex is blue and the rightmost vertex is green. Show that an odd number of the edges will be bichromatic.

2. (Intermediate value theorem) The Bolzano-Weierstrass theorem states that any bounded sequence in $R^{n}$ has a convergent subsequence. The intermediate value theorem states that if you have a continuous function $f : [0, 1] \to R$ such that $f (0) \leq 0$ and $f (1) \geq 0$ , then there exists an $x \in [0, 1]$ such that $f (x) = 0$ . Prove the intermediate value theorem. It may be helpful later on if your proof uses 1-D Sperner's lemma and the Bolzano-Weierstrass theorem

3. (1-D Brouwer fixed point theorem) Show that any continuous function $f : [0, 1] \to [0, 1]$ has a fixed point (i.e. a point $x \in [0, 1]$ with $f (x) = x$ ). Why is this not true for the open interval $(0, 1)$ ?

4. (2-D Sperner's lemma) Consider a triangle built out of $n^{2}$ smaller triangles as shown. Color each vertex red, blue, or green, such that none of the vertices on the large bottom edge are red, none of the vertices on the large left edge are green, and none of the vertices on the large right edge are blue. Show that an odd number of the small triangles will be trichromatic.

5. Color the all the points in the disk as shown. Let $f$ be a continuous function from a closed triangle to the disk, such that the bottom edge is sent to non-red points, the left edge is sent to non-green points, and the right edge is sent to non-blue points. Show that $f$ sends some point in the triangle to the center.

6. Show that any continuous function $f$ from closed triangle to itself has a fixed point.

7. (2-D Brouwer fixed point theorem) Show that any continuous function from a compact convex subset of $R^{2}$ to itself has a fixed point. (You may use the fact that given any closed convex subset $S$ of $R^{n}$ , the function from $R^{n}$ to $S$ which projects each point to the nearest point in $S$ is well defined and continuous.)

8. Reflect on how non-constructive all of the above fixed-point findings are. Find a parameterized class of functions where for each $t \in [0, 1]$ , $f_{t} : [0, 1] \to [0, 1]$ , and the function $t \mapsto f_{t}$ is continuous, but there is no continuous way to pick out a single fixed point from each function (i.e. no continuous function $g$ such that $g (t)$ is a fixed point of $f_{t}$ for all $t$ ).

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

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

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

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

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

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

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

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

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

Exercises / Problem-SetsFixed Point TheoremsLogic & Mathematics

Frontpage

Fixed Point Exercises

No comments64 karma

Diagonalization Fixed Point Exercises

13 comments46 karma

More from Scott Garrabrant

Curated and popular this week

40Comments

New Comment

40 comments, sorted by

top scoring

Click to highlight new comments since: Today at 8:02 PM

[-]nshepperd8y70

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.

[-]lbThingrb8y20

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

[-]Charlie Steiner8y20

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

[-]Hoagy8y70

Cleanest solution I can find for #8:

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

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

We take our closed convex set $S$ that has the bounded function

h : S \to S

. We take a triangle

T

that covers

S

so that any point in

S

is also in

T

Now we define a new function

h^{'} : T \to T

such that

h^{'} (x) = h (c_{s} (x))

where

c_{s} (x)

is the function that maps

x

to the nearest point in

S

By #6 we know that

h^{'}

has a fixed point, since

c_{s}

is continuous. We know that the fixed point of

h^{'}

cannot lie outside

S

because the range of

h^{'}

S

. This means

h^{'}

has a fixed point within

S

and since for

x \in S

h (x) = h^{'} (x)

h

has a fixed point.

[-]Chris_Leong8y30

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.

[-]Adele Lopez8y50

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.

[-]lbThingrb8y40

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

[-]Adele Lopez8y20

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

[-]jessicata8y51

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.

[-]riceissa8y50

My solution for #3:

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

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

[-]Charlie Steiner8y30

Yeah, I did the same thing :)

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

[-]Chris_Leong8y30

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

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

[-]Gurkenglas8y50

If #4 is true, it is provable:

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

#8:

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

[-]Paul Crowley8y50

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

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

[-]Chris_Leong8y40

Here's a more conceptual framing:

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

[-]Rafael Harth8y40

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

Call the large triangle a graph and the

n^{2}

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

Label the three colors

x, y

, and

z

. Let

v

be the node being recolored, wlog from

x

y

. Suppose first that

v

has six neighbors. It is easy to see that a triangle between

v

and two neighbors has changed if and only if one of the neighbors has color

z

and the other has color

x

y

. Thus, we must show that the number of such triangles is even. If all neighbors have color

z

, or if none of them do, then no triangles have changed. If exactly one node has color

z

, then the two adjacent triangles have changed. Otherwise, let

j

and

k

denote two different neighbors of color

z

. There are two paths using only neighbors of

v

between

j

and

k

. Both start and end at a node of color

z

. By the 1-D Sperner Lemma (assuming the more general result), it follows that both paths have an even number of edges between nodes of color

z

and

{x, y}

; these correspond to the triangles that have changed.

v

is a node on one of the graph's boundaries changing color from

x

y

, it has exactly 4 neighbors and three adjacent triangles. The two neighbors that are also on the boundary cannot have color

z

, so either none, one, or both of the ones that aren't do. If it's none, no triangle has changed; if it's one, the two neighboring triangles have changed; and if it's both, then the two triangles with two nodes on the graph's boundary have changed.

[-]Chris_Leong8y40

Some preliminary thoughts on q9:

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

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

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

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

[-]gjm8y40

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

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

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

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

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

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

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

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

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

[-]Chris_Leong8y40

Rough approach for qu 6:

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

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

[-]TheWakalix8y30

Strategies that I've found helpful:

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

Specific solutions (or suggestive handwaving):

Problem 1:

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

Problem 2:

I couldn't understand this one at first. After checking Wikipedia, I think that

R_{n}

refers to the space that each point in the sequence lies within. An example of a finite sequence in

R_{2}

would then be

(1, 2), (3, 1), (5, 3)

Problem 3:

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

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

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

f (x) = x^{2}

should work.

[-]Rafael Harth8y30

Ex 1

Let

V = {v_{0}, . . ., v_{n}}

and

e_{k} := (v_{k - 1}, v_{k})

. Given an edge

e

, let

ϕ_{e}

denote the map that maps the color of the left to that of the right node. Given a

k \in {1, . . ., n}

, let

ϕ_{k} = ϕ_{e_{k}} \circ . . . \circ ϕ_{e_{1}}

. Let

b

denote the color blue and

g

the color green. Let

c (k)

be 1 if edge

e_{k}

is bichromatic, and 0 otherwise. Then we need to show that

ϕ_{n} (b) = g ⟹ (\sum_{k = 1}^{n} c (k)) is odd

. We'll show

(\sum_{k = 1}^{n} c (k)) is even ⟺ ϕ_{n} (b) = b

, which is a striclty stronger statement than the contrapositive.

For

n = 1

, the LHS is equivalent to

c (ϕ_{1}) = 1

, and indeed

ϕ (e_{1}) (b)

equals

g

e_{1}

is bichromatic, and

b

otherwise. Now let

n > 1

and let it be true for

n - 1

. Suppose

\sum_{k = 1}^{n} c (k) is even

. Then, if

c (e_{n}) = 1

, that means

(\sum_{k = 1}^{n - 1} c (k)) is odd

, so that

ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (g) = b

, and if

c (e_{n}) = 0

, then

(\sum_{k = 1}^{n - 1} c (k)) is even

, so that

ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (b) = b

. Now suppose

\sum_{k = 1}^{n} c (k) is odd

. If

c (e_{n}) = 1

, then

(\sum_{k = 1}^{n - 1} c (k)) is even

, so that

ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (b) = g

, and if

c (e_{n}) = 0

, then

(\sum_{k = 1}^{n - 1} c (k)) is odd

, so that

ϕ_{n} (b) = ϕ_{e_{n}} (ϕ_{n - 1} (b)) = ϕ_{e_{n}} (g) = g

. This proves the lemma by induction.

Ex 2

Ordinarily I'd proof by contradiction, using sequences, that

inf {x \in [0, 1] | f (x) > 0}

can neither be greater nor smaller than 0. I didn't manage a short way to do it using the two lemmas, but here's a long way.

Set

x_{0} = 0

. Given

n \in N_{+}

, let

G_{n}

be a path graph of

n + 1

vertices

{v_{n, 0}, . . ., v_{n, n}}

, where

v_{n, k} = \frac{k}{n}

. If for any

n

and

k

we have

f (v_{n, k}) = 0

, then we're done, so assume we don't. Define

c (v, v^{'})

to be 1 if

f (v)

and

f (v^{'})

have s different sign, and 0 otherwise. Sperner's Lemma says that the number of edges

e

with

c (e) = 1

are odd; in particular, there's at least one. Let the first one be denoted

(v, w)

, then set

x_{n} = max {v, x_{n - 1}}

Now consider the sequence

(x_{n})_{n \in N}

. It's bounded because

x_{k} \in [0, 1]

. Using the Bolzano-Weierstrass theorem, let

(x_{n}^{'})_{n \in N} \mapsto x^{*}

be a convergent subsequence. Since

f (x_{k}) > 0

for all

k \in N_{+}

, we have

f (x^{*}) \geq 0

. On the other hand, if

f (x^{*}) > 0

, then, using continuity of

f

, we find a number

x^{'} > x^{*}

such that

f (x^{*}, x^{'}) > 0

. Choose

n

and

k

such that

v_{n, k} \in (x^{*}, x^{'})

, then

c (v_{n, j}) = 0

for all

j < k

, so that

x_{n} \geq v_{n, k} > x^{*}

and then

x_{ℓ} \geq x_{n}

for all

ℓ \geq k

, so that

x^{*} \geq x_{n} \geq v_{n, k} > x^{*}

, a contradiction.

Ex 3

Given such a function

f

, let

g : [0, 1] \mapsto [- 1, 1]

be defined by

g (x) = f (x) - x

. We have

g (0) = f (0) - 0 \geq 0 \geq f (1) - 1 = g (1)

. If either inequality isn't strict, we're done. Otherwise,

g (0) > 0 > g (1)

. Taking for granted that the intermediate value theorem generalizes to this case, find a root

x^{*}

g

, then

f (x^{*}) = f (x^{*}) - x^{*} + x^{*} = g (x^{*}) + x^{*} = x^{*}

[-]Charlie Steiner8y30

#8 actually comes up in physics:

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

[-]Charlie Steiner8y30

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

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

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

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

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

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

[-]Chris_Leong8y30

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

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

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

[-]Hoagy8y30

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

This isn't a problem if we just increase the number n by which we divide the whole triangle instead of recursively dividing subtriangles. Unfortunately now we're not reducing the range of co-ords where this fixed point must be, only finding a triad of arbitrarily close points that map to a triangle surrounding the centre. You can, for example, take the centre point of the first of these triangles (with some method of numbering to make the function definite) for each value of

n = 1, 2, 3..

as a sequence in

R^{2}

. This must have a convergent sequence which should converge to a point that maps to the centre but I can't prove that last stage.

[-]Chris_Leong8y30

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

[-]Chris_Leong8y30

Here's a solution to 4:

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

------

Proof of Lemma:

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

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

R R R R R

R G G G R

R G R B R

R G G G R

R R R R R R

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

END EDIT

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

g g g

g b r g

g g g

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

g g g

g r g g

g b r g

g r g g

g g g

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

[-]Davidmanheim8y30

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

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

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

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

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

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

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

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

Pointers welcome!

[-]Adele Lopez8y40

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

[-]Hoagy8y40

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

First let's separate all of the red nodes into groups so that within each group you can get to any other node in that group only passing through red nodes, but not to red nodes in any other group.

Now, we trace out the paths that surround these groups - they immediately look like the paths from Question 1 so this feels like a good start. More precisely, we draw out the paths such that each vertex forms one side of a triangle that has a blue node at its opposite corner. Note that you can have multiple paths stemming from the same group if the group touches the side of the larger triangle, or if it has internal holes.

Now we have this set of paths we can split them into three kinds. The first is loops, which arise when you have a group which never touches the edge of the larger triangle, or inside 'holes' in large groups. These can be seen as a path starting and finishing at the same node. They therefore have an even number of b-g vertices. The second kind is those that begin at the edge of the large triangle and end at the same edge. These paths begin and end on the same colour and therefore also have an even number of b-g vertices. Finally and most importantly there is a kind of path that goes from one edge to the other -in the case of the reds, the left edge to the right edge. This will happen once with the group that includes the top red node, and if any other group spans the larger triangle then it will generate two more of these paths. Sperner's lemma tells us that these will have an odd number of b-g vertices and we know that there will be an odd number of such paths, so this final type generates an odd number of total b-g vertices.

By the way that we have defined these paths, the total number of r-g-b triangles is equal to the number of g-b vertices on the paths in the set generated above. This number is the sum of an odd number from the spanning paths and a series of even numbers from the other paths, giving an odd overall number of r-g-b vertices, proving number 4 (as long as I haven't made an error in categorizing the paths).

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

[-]Davidmanheim8y30

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

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

[-]Hoagy8y60

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

You can map the continuous function f(x) to a path of the kind found in Question 1 of length n+1
by evaluating f(x) at x=0, x=1 and n-1 equally spaced divisions between these two points and setting a node as blue if f(x) < 0 else as green.

By Sperner's Lemma there is an odd, and therefore non-zero number of b-g vertices. You can then take any b-g pair of nodes as the starting points for a new path and repeat the process. After k iterations you have two values of x - only one where f(x) is below zero - that are 1/(n^k) away from each other. We thus can find arbitrarily close points that straddle zero. By taking the sequence f(x) of initial nodes x we get a sequence that, by B-W, has a sub-sequence which converges to zero. By continuity we have proved the existence of an x such that f(x)=0.

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

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

[-]riceissa8y30

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?

[-]Chris_Leong8y40

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

[-]Hoagy8y30

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

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

[-]Czynski8y20

I hit that stumbling block as well. I handwaved it by saying "continue iterating until you have

x_{(k, B)}

and

x_{(k, G)}

such that

f (x_{k, B}) < 0

f (x_{k, G}) \geq 0

, and f has no local maxima or local minima on the open interval

(x_{k, B}, x_{k, G})

", but that doesn't work for the Weierstrass function, which will (I believe) never meet that criterion.

[-]riceissa8y40

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

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

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

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

[-]Rafael Harth8y20

Ex 5 (fixed version)

Let

D

denote the triangle. For each

n \in N

, construct a 2-d simplex

S_{n}

with

(n + 1)^{2}

nodes in

D

, where the color of a point corresponds to the place in the disk that

f

carries that point to, then choose

x_{n}

to be a point within a trichromatic triangle in the graph. Then

(x_{n})_{n \in N}

is a bounded sequence having a limit point

x^{*}

. Let

t

be the center of the disc; suppose that

f (x^{*}) \neq t

. Then there is at least one region of the disc that

f (x^{*})

doesn't touch. Let

ϵ

be the distance to the furthest side, that is, let

ϵ = max {d (f (x^{*}), G), d (f (x^{*}), R), d (f (x^{*}), B)}

. Since the sides are closed regions, we have

ϵ > 0

. Using continuity of

f

, choose

δ \in R_{+}

small enough such that

B_{d} (x^{*}, δ) \subset B_{d} (f (x^{*}), ϵ)

. Then choose

n \in N

large enough so that (1) all triangles in

S_{n}

have diameter less than

\frac{δ}{2}

and (2)

d (x_{n}, x^{*}) < \frac{δ}{2}

. Then, given any other point

y

in the triangle around

x_{n}

S_{n}

, we have that

d (y, x^{*}) \leq d (y, x_{n}) + d (x_{n}, x^{*}) < \frac{δ}{2} + \frac{δ}{2} = δ

, so that

d (f (y), f (x^{*})) < ϵ

. This proves that the triangle in

S_{n}

does not map points to all three sides of the disc, contradicting the fact that it is trichromatic.

Ex 6

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

(Assume the triangle

T = ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ A B O

is equilateral.) Imbed

T

into

R^{2}

such that

O = (0, 0)

A = (- \frac{1}{2}, \frac{1}{2} \sqrt{3})

B = (\frac{1}{2}, \frac{1}{2} \sqrt{3})

. Let

f : T \mapsto T

be continuous. Then

h : T \mapsto R^{2}

given by

h : x \mapsto f (x) - x

is also continuous. If

h (x) = O = (0, 0)

then

(0, 0) = h (x) = f (x) - x ⟹ f (x) = x

. Let

R

be the circle with radius 2 around

O

; then

h (T) \subset R

because

| | h (x) | | = | | f (x) - x | | \leq | | f (x) | | + | | x | | \leq 2

(it is in fact contained in the circle with radius 1, but the size of the circle is inconsequential). We will use exercise 5 to show that

h

maps a point to the center, which is

O

, from which the desired result follows. For this, we shall show that it has the needed properties, with the modification that points on any side may map precisely into the center. It's obvious that weakening the requirement in this way preserves the result.

Rotate the disk so that the red shape is on top. In polar coordinates, the green area now contains all points with angles between

60^{\circ}

and

180^{\circ}

, the blue area contains those between

180^{\circ}

and

300^{\circ}

, and the red area those between

0^{\circ}

and

60^{\circ}

and those between

300^{\circ}

and

360^{\circ}

. We will show that

h (¯ ¯¯¯¯¯¯ ¯ A B)

does not intersect the red area, except at the origin. First, note that we have

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

Since both

T

and

¯ ¯¯¯¯¯¯ ¯ A B

are convex combinations of finitely many points, it suffices to check all combinations that result by taking a corner from each. This means we need to check the points

A - A

and

B - A

and

C - A

and

A - B

and

B - B

and

C - B

Which are easily computed to be

(0, 0)

and

(- 1, 0)

and

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

and

(1, 0)

and

(0, 0)

and

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

Two of those are precisely the origin, the other four have angles

270^{\circ}

and

150^{\circ}

and

90^{\circ}

and

210^{\circ}

. Indeed, they are all between

60^{\circ}

and

300^{\circ}

Now one needs to do the same for the sets

T - ¯ ¯¯¯¯¯¯ ¯ O A

and

T - ¯ ¯¯¯¯¯¯ ¯ B O

, but it goes through analogously.

[-]Gram Stone8y20

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

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

Theorem. Let

G = (V, E)

e a path graph on

n

ertices with a vertex

2

oloring

c : V \mapsto {0, 1}

uch that if

d e g (u) = d e g (v) = 1

hen

c (u) \neq c (v)

Let

S := {e \in E ∣ e

s bichromatic

}

Then

| S |

s odd.

Proof. By the definition of a path graph, there exists a sequence

{⟨ v_{k} ⟩}_{1 < k \leq n}

ndexing

V (G)

An edge

e_{k} = {v_{k}, v_{k + 1}}

s bichromatic iff

c (v_{k}) \neq c (v_{k + 1})

A subgraph

H

G

s a state iff its terminal vertices are each incident with exactly one bichromatic edge or equal to a terminal vertex of

G

The color of a state is the color of its vertices. There exists a subsequence of

⟨ v_{k} ⟩

ontaining the least term of each state; the index of a state is equal to the index of its least term in this subsequence.

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

For each state

H

there exists a subsequence of

⟨ v_{k} ⟩

orresponding to the vertices of

H

and the least term of each subsequence is either

v_{1}

r some

v_{k}

hat is the greatest term in a bichromatic edge. Thus the number of states in

G = 1 + | S |

By contradiction, suppose that

| S |

s even. Then the number of states is odd, and the first and last states are the same color, so the terminal vertices of

G

re the same color, contrary to our assumption that they are different colors. Thus

| S |

ust be odd.

:::

[-]Gurkenglas8y40

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

Moderation Log