Ahlswede-Zhang identity |

Rudolf Ahlswede

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 $\mathcal{F}$ of subsets of $[n]$ antichain if no set of $\mathcal{F}$ is contained in another.

LYM inequality: Let $\mathcal{F}$ be an antichain. Then $\sum_{A \in \mathcal{F}} {n \choose |A|}^{-1} \leq 1$ .

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 $\sum_{A \in \mathcal{F}} |A|!(n-|A|)! \leq n!$ . This suggests that a double counting argument of permutations may turn out to be of use to us. Indeed!

Proof: Let $S$ be the set of $n!$ permutations of the set $[n]$ . Let us say that a permutation contains $A \in \mathcal{F}$ if the first $|A|$ elements of the permutation form $A$ . Obviously, any $A \in \mathcal{F}$ is contained in $|A|!(n-|A|)!$ permutations. Since $\mathcal{F}$ is an antichain any permutation contains at most 1 set $A$ . Hence the result follows. QED

Notice that the Bollobás-LYM inequality can be rewritten as $\sum_{i=0}^n \frac{|\mathcal{F} \cap {[n] \choose i}|}{{n \choose i}} \leq 1$ . We also obtain the following corollary which is known as Sperner’s lemma.

Sperner’s Lemma: Let $\mathcal{F}$ be an antichain. Then $|\mathcal{F}| \leq {n \choose \lfloor \frac{n}{2} \rfloor}$ .

Proof: $|\mathcal{F}|=\sum_{i=0}^n|\mathcal{F} \cap {[n] \choose i}|\leq {n \choose \lfloor \frac{n}{2} \rfloor}\sum_{i=0}^n \frac{|\mathcal{F} \cap {[n] \choose i}|}{{n \choose i}}$ . 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 $A_1,\ldots,A_m$ and $B_1,\ldots,B_m$ be two sequences of sets such that $A_i \cap B_j = \emptyset$ if and only if $i=j$ . Then $\sum_{i=1}^m {a_i+b_i \choose b_i}^{-1} \leq 1$ , where $a_i=|A_i|,b_j=|B_j|$ .

Proof: Let $X=\cup_i A_i \cup_i B_i$ be the universe. Let $|X|=n$ . We will prove the inequality using a double counting argument. Specifically, let our $M$ matrix (see my previous post on double counting) be an $m \times n!$ matrix. Each row corresponds to a pair $(A_i,B_i)$ and each column to each permutation of the set $X$ . Now we decide how we place the 1s in our matrix. We will set $M_{ij}=1$ if the $i$ -th pair $(A_i,B_i)$ has the property that every element in $A_i$ comes before any element of $B_i$ in the $j$ -th permutation. Now things become way easier. The number of ones per row is $\frac{n!}{{a_i+b_i \choose b_i}}$ 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 $\mathcal{F}$ as $U(\mathcal{F})=\{ X \in 2^{[n]}: \exists A \in \mathcal{F}, A \subseteq X\}$ . Finally, for a set $X \in 2^{[n]}$ and every $\mathcal{F} \subseteq 2^{[n]}$ we define $X_{\mathcal{F}}=\cap_{\mathcal{F} \ni A \subseteq X}$ and $W_{\mathcal{F}}(X)=|X_{\mathcal{F}}|$ .

Ahlswede-Zhang identity: $\sum_{A \in \mathcal{F}} {n \choose |A|}^{-1}+\sum_{A \in U(\mathcal{F})-\mathcal{F}} \frac{W_{\mathcal{F}}(A)}{|A|{n \choose |A|}}=1$ .

According to the Wikipedia article Rudolf Ahslwede died recently. Here is a video dedicated to his memory and the legacy he left.

Tags: Ahlswede, Bollobas, double counting, LYM

Ahlswede-Zhang identity

Leave a Reply Cancel reply

Follow webpage via email

Ahlswede-Zhang identity

Share this:

Like this:

Leave a Reply Cancel reply

Follow webpage via email