Sperner's Theorem
Idea · Advanced
Combinatorics
Let
A family of subsets
is called an antichain if no two distinct sets in ℱ contain one another.
In other words, for distinct
we have
Sperner's Theorem
If ℱ is an antichain of subsets of [n], then
Equivalently,
The bound is attained by taking all subsets of the same middle size.
For example, if n = 6, take all 3-element subsets:
There are
such subsets, and none can contain another because they all have the same size.
Therefore, the largest possible antichain has
members.
LYM Inequality
A stronger result is the Lubell–Yamamoto–Meshalkin (LYM) Inequality:
Since
the LYM inequality immediately implies Sperner's Theorem.
A maximal chain is a sequence
where
Thus, at each step, exactly one new element is added.
Number of Maximal Chains
Every permutation
of [n] determines exactly one maximal chain:
Conversely, every maximal chain determines exactly one permutation.
Therefore, the number of maximal chains is
How Many Chains Contain a Given Set?
Let A be a subset of [n] with
For a maximal chain to contain A, the k elements of A must appear first in the corresponding permutation.
They can be ordered in
ways, while the remaining n − k elements can be ordered in
ways.
Therefore, A belongs to exactly
maximal chains.
Apply the Antichain Condition
Let ℱ be an antichain.
A maximal chain can contain at most one member of ℱ, because any two sets in the same chain are comparable by inclusion.
Therefore, counting pairs
where A belongs to ℱ and C is a maximal chain containing A, gives
This is the LYM inequality.
A collection contains 300 distinct subsets of
Prove that two of them satisfy
By Sperner's Theorem, an antichain can contain at most
sets.
Since
the collection cannot be an antichain.
Therefore, there exist distinct sets A and B such that
Let ℱ be a family of subsets of [12] such that no member of ℱ contains another.
Suppose every member has either 5 or 6 elements.
If ℱ contains 300 sets of size 5, prove that the number of sets of size 6 is at most 574.
Let x be the number of sets of size 6.
From the LYM inequality,
Since
we get
Thus
Therefore
Twenty singers want to perform a series of concerts.
At each concert, some of the singers perform on stage while the others listen from the audience. Two singers who are both performing at the same time cannot hear each other.
What is the minimum number of concerts required so that every pair of singers has heard each other sing?
For each singer, consider the set of concerts in which that singer performs.
Suppose singers A and B correspond to sets
For A to hear B, there must be a concert in which B performs and A does not. Thus,
Similarly, for B to hear A,
Therefore, for every two distinct singers,
Hence the 20 sets corresponding to the singers must form an antichain.
If there are n concerts, Sperner's Theorem tells us that the largest possible antichain has size
For n = 5,
so 5 concerts are not enough.
For n = 6,
So 6 concerts are enough: assign each singer a different 3-element subset of the 6 concerts, and let that singer perform exactly at those three concerts.
For any two distinct 3-element subsets A and B,
so each singer performs at least once while the other is in the audience.
Therefore, each pair hears each other sing.