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. :)
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. :)
Awesome! I was hoping that there would be a way to do this!