Theorem 37: Sperner’s lemma

I’ve written about various theorems in combinatorics so far, but I don’t think any of them have the flavour of today’s theorem.

We’re going to concentrate on the set , which I might sometimes write as (that’s standard notation in combinatorics).  This set has lots of subsets, such as , and itself, and (the empty set, which contains no elements at all).  How many such subsets? 

Well, there are elements, each of which either belongs or does not belong to any given subset.  So there are possibilities for whether a given element belongs to a given subset, so subsets in total.  Write out the subsets of , say, if you don’t believe me!

How can we think about these subsets?  There are two helpful pictures I have in mind; sometimes one is more convenient, sometimes the other.

Here’s the first, which might explain why mathematicians sometimes talk of this object (the family of subsets of ) as the cube.  My limitations when it comes to graphics software mean that I’ve written for , the empty set.

Hopefully this picture will make it all clear, and I don’t need to say anything.  But there is one thing I want to say.  This picture shows a graph (in the combinatorics sense), in which the vertices are the subsets of , and two subsets are joined exactly when they differ by just one element.  By positioning the vertices carefully, I end up with a picture that we all recognise as a cube.  But if you’re struggling to imagine a 15-dimensional cube, don’t worry about it: we can think about it more abstractly, without needing to draw a picture.  (I can draw representations of the 4-, 5- and 6-dimensional cubes if necessary, though — I’ll leave that for you to think about.)

What’s the other way of thinking about this family of subsets?  I’m going to call this the layered model (I don’t know of a standard term for it).  Each layer contains all the subsets of the same size.  So here it is for .  I’ve written in what the various subsets are, but normally I’d just draw the blobs without the subsets.

Notice that the top and bottom blobs are the same size because they contain the same number of sets, and similarly the second and third blobs are the same size.  In general, the picture would look something like this.

The picture on the left is for even; the picture on the right is for odd.  Why the difference?  If is even, then the largest layer will correspond to subsets of size (exercise: prove this!).  If is odd, then there are two largest layers, corresponding to subsets of size and (that is, and ).  Again, I’ll leave this for you to prove.

Now, what sort of questions can we ask about the family of subsets of ?

Here’s one.  The family contains some chains.  Here’s a linguistic analogy.  Have you come across those word puzzles where each answer uses the letters of the previous answer, plus a new letter?  For example, the chain of answers might be: A, AT, PAT, TAPS, PASTE, PLATES, STAPLER, PRATTLES (to give an example off the top of my head).  A chain in the family of subsets uses the same idea, but adding new elements of each time, rather than new letters.  For example, here’s a chain in : the collection , , , , .  And here’s another: , , .

Formally, a chain is a collection of subsets where for each pair of subsets  and in the chain, either or .  So the subsets are nicely nested.    Get the idea?

So what’s the question?  If you’re like me, you’ll have looked at my chain of words above, and wondered whether we could add another word on the end.  (I didn’t try very hard, so it may well be possible.)  And could I have made a longer chain, if I’d started in a different place or chosen a different option?  In fact, what’s the longest possible chain of words like this (bearing in mind that we have 26 letters to choose from)?

Well, we could ask the same question about chains in .  (And since we’re only after subsets, rather than valid English words, it might be an easier problem!)  So: what’s the length of the longest chain in ?

It’s pretty easy to see that we can always have a chain of length .  I gave an example of such a chain when , and hopefully you can see how this generalises.  (Notice that I’m not claiming this is the only example of a long chain: there are lots!)

Can we ever have a longer chain?

Here’s where the layer picture helps us a lot.  I’m imagining a chain as a line working from top to bottom (or bottom to top!) through the layers.  Could the chain ever have two sets from the same layer?  Err…quick think…no.  (Do you agree?)  So any chain contains at most one subset from each layer.  And how many layers are there?  Err…quick think…, right?  Oh, but that means any chain has length at most , and since we’ve already seen that length is possible, that must be the answer!

That didn’t detain us for very long.  (I bet it’s much harder to solve the problem with words!)

Let’s ask a different question, perhaps the opposite question, in a way.  What happens if, instead of insisting that every subset contains or is contained in every other subset, we instead say that no subset can contain or be contained in another?  (I feel confident that one could generate a very, very long list of words like that, so I’m not even going to bother!)  We’ll call the resulting objects antichains.  (Some people call them Sperner families, but I prefer `antichain’ because it seems more descriptive.)

Here’s an example in : , , .  No subset contains or is contained in any other, right?  Could we make that antichain longer?  Yes, we could add , but not anything else.  (Check this!)  But could we have made a longer antichain by starting in a different place?  What’s the length of the longest possible antichain?  And what’s the length of the longest possible antichain for general ?