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.

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: