This post is about Sperner systems and about turning the famous LYM inequality into an identity. Typically, people refer to this inequality as the LYM inequality (Lubell-Yamamoto-Meshalkin) but it is worth pointing out that the inequality follows as a corollary from the more general Bollobás inequality. While thinking of this inequality I asked myself about the cases that it turns out to be tight. The answer and more was given by an identity which I am going to state here. It is due to Ahlswede and Zhang and precisely characterizes the deficiency of the Bollobás-LYM inequality. We start by the definition of a Sperner System, also called antichain. We shall call a family of subsets of antichain if no set of is contained in another.
LYM inequality: Let be an antichain. Then .
Since the proof is few lines long we sketch it here. Before we see it though let us see the rationale behind it. We may rewrite . This suggests that a double counting argument of permutations may turn out to be of use to us. Indeed!
Proof: Let be the set of permutations of the set . Let us say that a permutation contains if the first elements of the permutation form . Obviously, any is contained in permutations. Since is an antichain any permutation contains at most 1 set . Hence the result follows. QED
Notice that the Bollobás-LYM inequality can be rewritten as . We also obtain the following corollary which is known as Sperner’s lemma.
Sperner’s Lemma: Let be an antichain. Then .
Proof: . The result follows directly now. QED
Let’s see before going in the Ahlshwede-Zhang identity the Bollobás inequality. It is a “must-know” in extremal combinatorics with many applications.
Bollobás inequality: Let and be two sequences of sets such that if and only if . Then , where .
Proof: Let be the universe. Let . We will prove the inequality using a double counting argument. Specifically, let our matrix (see my previous post on double counting) be an matrix. Each row corresponds to a pair and each column to each permutation of the set . Now we decide how we place the 1s in our matrix. We will set if the -th pair has the property that every element in comes before any element of in the -th permutation. Now things become way easier. The number of ones per row is and each column has at most 1 (verify these two things on your own!). The result follows directly. QED
Finally, what the title of the post is about. I will post more about it in the near future since it got a bit late :). Let’s define the upset generated by as . Finally, for a set and every we define and .
Ahlswede-Zhang identity: .
According to the Wikipedia article Rudolf Ahslwede died recently. Here is a video dedicated to his memory and the legacy he left.