LYM-Related AZ-Identities, Antichain Splittings and Correlation Inequalities
- PDF / 592,687 Bytes
- 47 Pages / 595.276 x 841.89 pts (A4) Page_size
- 28 Downloads / 155 Views
LYM-Related AZ-Identities, Antichain Splittings and Correlation Inequalities
Lecture 13 LYM-Type Relations In this lecture we present proofs of several relations that are improvements and generalizations of the so-called LYM (Lubell-Yamamoto-Meshalkin) inequality. Initially this inequality set a relation for the distribution of cardinalities of members in an antichain of subsets. A family A ⊂ 2[n] is a chain if any two sets A1 , A2 ∈ A are comparable, that is, A1 ⊂ A2 or A2 ⊂ A1 . Obviously the maximal length of a chain is n + 1. A family A ⊂ 2[n] is an antichain if any two sets A1 , A2 ∈ A are incomparable, that is, A1 ⊂ A2 and A2 ⊂ A1 . Obviously the family of k-sets A ⊂ [n] k is an antichain n and Sperner’s Lemma says that the antichain |A| = n has maximal size (and it 2 also settles the uniqueness property discussed below). The upper bound |A| ≤ nn 2 is not obvious and follows from the LYM inequality. If f0 , f1 , . . . , fn is a sequence such that fi = A ∩ [n]i for some antichain A, then the LYM inequality says that n
fi
i=0
i
∑ n ≤ 1.
Hence n
|A| = ∑ fi ≤ i=0
n
n2
(1)
n
fi ∑ n ≤
i=0
i
n
n2
.
The main statement of Sperner’s Lemma follows. This lecture has only one section. Here we investigate the possibility of improving the LYM inequality (1). Actually taking into account other terms we derive the so-called AZ (Ahlswede–Zhang) identity. we consider the uniqueness of the antichain A for which equality Also |A| = nn is achieved and related problems. In Theorems 28 and 30 we demon2 strate further generalizations of the AZ-identity. The proof of Theorem 29 is similar to the proof of the AZ-identity and we ask to do it in Exercise 1.
151
152
V LYM-Related AZ-Identities, Antichain Splittings and Correlation Inequalities
Let us give some definitions. For every X ∈ 2[n] and every A ⊂ 2[n] we define ,
XA =
A, WA (X) = |XA |.
X⊃A∈A
Using the functions (i)
WA =
∑
WA (X)
X∈([n] i)
we can write
(i)
n W WA (X) ∑ |X| n = ∑ iAn . X i=1 |X| i
§1 The AZ-Identity and Related Results We start with the proof of the following: Theorem 27 (Ahlswede and Zhang 1990) For every family A of nonempty subsets of [n] n
W
(i)
∑ iAn = 1.
i=1
(2)
i
Identity (2) is called the AZ-identity. When A is an antichain, identity (2) becomes
∑
1 n+
X∈A |X|
WA (X) n = 1, X∈U (A)\A |X| |X|
∑
(3)
where U(A) = {Y ∈ 2[n] : ∃A ∈ A, A ⊆ Y } is the upset generated by A. Hence (2) is a strengthening of the LYM inequality, whose deficiency can be measured by the second summand. Proof. Note first that only minimal elements in A determine XA and therefore matter. Hence we can assume that A is an antichain. The LYM inequality is obtained as follows. All saturated chains (saturated means that the chain is not contained in a larger chain), which pass through members of A, are counted: ∑ |A|!(n − |A|)!. A∈A
No chain is counted twice, because A is an antichain. Since there are n! saturated chains in total, clearly ∑ |A|!(n − |A|)! ≤ n!. A∈A
Lecture 13
Data Loading...
