Theorem 40: Sperner’s lemma about coloured triangles

I have a difficulty with this post, namely that I’ve previously written about a result called Sperner’s lemma, and this is a different one!  I hope this won’t cause any confusion.

As the title suggests, this post is about coloured triangles.  That’s not quite accurate, actually, but it was the best I could do in a short title.  Now that I have more space, let me be a bit more precise.

Draw a triangle.  Any triangle.

Subdivide it into little triangles, in any way you like.

Like this:  or like this:  for example.

Now you need three coloured pens.  I’m going to assume that they are blue, red and green.

Colour one vertex of your triangle blue, one red, and one green.

OK so far?

Now you’re going to colour the vertices of all the little triangles.  There are just two rules.

If a vertex is on the edge with red at one end and blue at the other, then you can colour it either red or blue but not green.  And similarly for the other edges: you can use either of the colours at the end of the edge, but not the third.

And you can colour the vertices inside the triangle in any way you choose.   Here’s my example.

All done?

Now I predict that … actually, I’ll wait to make my prediction.  Why don’t you see whether you can guess what my prediction is, and then you can check over the fold.

You might also like to try the Triangle Game on NRICH.

My prediction is … that at least one of your little triangles has one red vertex, one green, and one blue.  Is that the prediction that you expected?

Of course, I can’t see how you’ve coloured your triangle so my prediction must be based on some deeper phenomenon.  And that phenomenon is Sperner’s lemma.

Theorem (Sperner): Let T be a triangle, subdivided into smaller triangles (a triangulation).  Colour the vertices of the triangulation using three colours, according to the following rules:

  • T has exactly one vertex of each colour;
  • if a vertex is on an edge of T, then it must be coloured using one of the two colours at the ends of that edge;
  • the vertices inside T can be coloured in any way.

Then there is a small triangle in the triangulation that has exactly one vertex of each colour.

So how does one go about proving something like this?  There are a number of ways.  I’d like to talk about one particular proof, because it’s such a pretty idea.  To help you follow this proof, I suggest that you draw up a triangulation — make it a fairly large picture, as you’re going to need to add labels to it!  And colour the vertices of your triangulation according to the rule above.

You’re now going to label each edge of the triangulation.  In fact, you are going to label each interior edge twice, once on either side.  Ready?

Pick a small triangle.  You will need to think of going clockwise or anticlockwise round your small triangle.  Now label the edges according to the following rules.  (I suggest that you record the label just next to the edge, inside the triangle.)  Pick one edge of your special triangle.

  • If the vertices at the ends of your edge have the same colour, then label the edge 0.
  • If the vertices at the ends of your edge have different colours and, going clockwise round your small triangle these colours come in the same order as going clockwise round the big triangle T, then label the edge 1.
  • If the vertices at the ends of your edge have different colours and, going clockwise round your small triangle these colours come in the same order as going anticlockwise round the big triangle T, then label the edge -1.

Do this for each edge of each small triangle (remembering to label internal edges twice, once for each of the small triangles of which it is an edge).

OK?  Here’s an example to help you check. 

Did you notice anything interesting?

Let’s think about what happens as we go along an edge of the triangle T, moving clockwise around the triangle.  We may as well ignore the edges labelled 0 — they’re not interesting.  If we think about it for a moment, we can see that the number of edges labelled 1 must be one more than the number of edges labelled -1, because the overall effect is a 1.  Another way of saying that is that the sum of the labels on an exterior edge must be 1.  Somehow the rest of this argument is an adaptation of that idea to two dimensions (using the one-dimensional argument on a line as a key ingredient).

Now that you have labelled the edges of each small triangle, you can label the triangles themselves.  To do this, simply add the numbers on the three edges of the triangles.  You might like to put the label in the centre of the triangle, perhaps with a circle round it to make it stand out.  Like this:

Did you notice any interesting features?

Now let’s try adding up these numbers in a couple of ways (knowing that we must get the same answer!).

Way 1.  The internal edges are all labelled so that the sum of the two labels on either side is 0, right?  Either both sides are 0, or one side is 1 and the other is -1.  So if we add all the labels on the internal edges, we get 0.  What do the outer edges contribute?  As we go from one vertex of T to another, passing along an edge (and going clockwise round the triangle), we know that the sum must be 1 because overall that’s the effect.  (Try this on your picture to convince yourself!)  So the labels on the outer edges must sum to 3.  So overall, if we add all the labels on all the edges then we get 3.

Way 2.  Just add the labels on the triangles.  Adding all these labels is exactly the same as adding all the labels on the edges.

So the labels on the triangles sum to 3.

What can we say about labels on triangles?  You must have found that they were 0, -3 or 3.  Can we explain that?

  • If all three vertices of a triangle have the same colour, then all three edges are labelled 0 and the sum is 0.
  • If two vertices of a triangle have one colour and the third has a different colour, then one edge is labelled 0, one edge is labelled -1 (going from one colour to another in one direction), and the third is labelled 1 (going from one colour to the other in the opposite direction).  So the sum is 0.
  • If all three vertices of a triangle have different colours, and these occur in the same order as on the vertices of T, then each edge is labelled 1 and so the sum is 3.
  • If all three vertices of a triangle have different colours, and these do not occur in the same order as on the vertices of T, then each edge is labelled -1 and so the sum is -3.

Now we add a bunch of these labels (0, 3 and -3) together and get 3.  What can we deduce?  Certainly that there is at least one triangle whose vertices have different colours (otherwise the sum would be 0), and in fact also that the number of clockwise triangles is one more than the number of anticlockwise triangles.  So it turns out that not only is there at least one triangle whose vertices have different colours, but also that the number of such triangles must be odd!  Which is pretty nice.

Why did I want to write about this?  Partly because it’s a very pretty result, and a very pretty proof.  And also because it turns out that Sperner’s lemma is very useful if you want to prove things about fixed points of maps.  I hope to write something relatively soon about Brouwer’s fixed point theorem, and Sperner’s lemma will be useful there.  Watch this space…

Further reading

Here’s a nice interactive tool to help you try this out for yourself.  NRICH has the Triangle Game and an explanatory article.  And of course there’s a Wikipedia page.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: