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.
Is there a way to make drafts available to specific people, for review?