6
$\begingroup$

enter image description here I noticed something about colored triangulations of the topological sphere $S^2$ and have a question about this.

Observation. If you triangulate the sphere $S^2$ and color the vertices with three colors: then the number of 3-colored triangles is always even (or zero). In particular, there is no coloring with exactly one 3-colored triangle.

For a proof, view $S^2$ as two triangulated disks with matching coloring of the boundaries that are glued together. As their boundaries have the same number of color changes, we know from Sperner’s Lemma that their triangulations have the same number (mod 2) of 3-colored triangles. So the total number of 3-colored triangles is even or zero.

As an interesting corollary, we get the characterization: A triangulated sphere has zero 3-colored triangles iff all cycles of the triangulation have an even number of color changes.

I looked at the torus, the Klein bottle, and the projective plane, and I find that the observation is also true for them.

Edit: Just for contrast, adding an example below of a "soap bubble" surface, where the two soap bubbles share a common disk. This surface allows for triangulations with even and odd numbers of 3-colored triangles (but like the other surfaces I looked at, cannot have just one).

Question. I wonder whether this also follows from more general theorems about triangulations of surfaces, or about maximal planar graphs? I have consulted algebraic topology and graph theory texts, but could not find any results in that direction. Would you have a suggestion where else to look, or maybe a reference for that?

enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ This looks related to Sperner's lemma: en.wikipedia.org/wiki/Sperner%27s_lemma $\endgroup$ – Jan Kyncl Jun 24 '20 at 22:51
  • 1
    $\begingroup$ @JanKyncl you are definitely right. It is like Sperner’s Lemma “without boundary”. Or the way I looked at it, 2 x Sperner’s Lemma and then glued together. Just in case you are interested, see this mathoverflow.net/q/362025/156936 $\endgroup$ – Claus Dollinger Jun 25 '20 at 3:47
  • $\begingroup$ "Uneven" numbers are commonly called odd. $\endgroup$ – Victor Protsak Jun 28 '20 at 19:57
  • $\begingroup$ @VictorProtsak thanks a lot for your comment! I corrected the wording in the text now. $\endgroup$ – Claus Dollinger Jun 29 '20 at 11:32
7
$\begingroup$

A counting proof shows that this observation is unrelated to the global topology.

Every edge is monochromatic or dichromatic. How many dichromatic edges are there? If each triangle tells you its number of dichromatic edges (either 0, 2, or 3), you can add these up and divide by two to get the total number of dichromatic edges (since every edge contributes to two triangles). So the number of trichromatic triangles must be even.

This proof works for $k$-dimensional manifolds when $k$ is even, since the number of $k$-colored $(k-1)$-simplices bounding any $k$-simplex must be 0, 2, or $k+1$.

Your corollary similarly transfers to higher even dimensions, at least for orientable manifolds, replacing "cycles of edges" with "hypersurfaces of $(k-1)$-simplices", and "even number of color changes" with "even number of $k$-colored $(k-1)$-simplices".

$\endgroup$
2
  • 2
    $\begingroup$ I'm not sure which direction you want to go in with this, but I think it falls pretty squarely in combinatorics and graph theory. What you (not incorrectly) call "triangulations of $S^2$" are often referred to as maximal planar graphs. My proof is very similar to the handshaking lemma. People have also considered coloring and planarity on tori and other manifolds. $\endgroup$ – Matt Jun 24 '20 at 19:32
  • $\begingroup$ thanks a lot for this helpful comment and great links. This is excellent $\endgroup$ – Claus Dollinger Jun 24 '20 at 20:20
3
$\begingroup$

Just to close the loop on this: the double-counting argument in the answer of user Matt allows for a nice visual proof of the (2-dim.) Lemma of Sperner. Just want to capture it here, as it connects nicely with the triangulation of the sphere / the maximal planar graph in my OP question.

enter image description here

Start with a triangulated polygon in the plane, and label each vertex with one of 3 colors. The example just shows the boundary of such a triangulated, 3-colored polygon. Claim (Sperner’s Lemma): If the boundary has an odd number of color changes, then a 3-colored triangle exists in the polygon triangulation. In fact, more generally, an odd number of such 3-colored triangles exists.

Proof: Go to 3-dimensional space, and build a “tent” over the polygon like in the diagram: add a colored vertex, and add the edges between this additional vertex and the boundary vertices of the polygon. This way, we have effectively created a triangulation of the topological sphere $S^2$.

If the boundary of the polygon has an odd number of color changes, this gives an odd number of 3-colored triangles in the “tent” over the polygon. But from the double-counting argument in user Matt’s answer, we know an even number of 3-colored Sperner triangles must exist. Hence the polygon at the bottom must have an odd number of 3-colored triangles (at least one) in its triangulation, which completes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.