MỘT TẬP A ⊂ [N] THÌ A CÓ THỂ VỪA THUỘC VÀO XÍCH C , VỪA THUỘC VÀO Đ...
2. Một tập A ⊂ [n] thì A có thể vừa thuộc vào xích C , vừa thuộc vào đối xích F . Do đó ta đi đếm số
cặp
N = { (A, C) | với C ∈ C và A là một tập hợp vừa thuộc xích C vừa thuộc đối xích F } .
• Với mỗi C ∈ C , có nhiều nhất một tập A mà A ∈ C và A ∈ F. Thật vậy, giả sử có hai tập
A
1, A
2vừa thuộc vào C, vừa thuộc vào F . Vì A
1, A
2thuộc xích C nên hoặc A
1⊂ A
2hoặc
A
2⊂ A
1, nhưng khi đó thì A
1, A
2không thể thuộc vào F được, vì các tập con của F không
có tập nào là tập con của tập khác. Vậy
| N | ≤ n!
• Với mỗi tập A ∈ F mà | A | = k. Khi đó có k! cách chọn các tập A
1, A
2, . . . , A
k−1(cách đếm
giống hệ ý 1) mà
A
1⊂ A
2⊂ . . . ⊂ A
k−1⊂ A, | A
i| = i, ∀ i = 1, 2, . . . , k − 1
và có (n − k)! cách chọn các tập A
k+1, . . . A
nmà
A ⊂ A
k+1⊂ . . . ⊂ A
n, | A
j| = j, ∀ j = k + 1, k + 2, . . . , n.
Suy ra mỗi A ∈ F ta có
k!(n − k)! = | A | !.(n − | A | )!
cách chọn xích C chứa A. Do đó
| N | = ∑
| A | !(n − | A | )!.
A∈FTừ hai cách đếm trên, ta có
| A | !(n − | A | )!
A∑
∈F| A | !(n − | A | )! ≤ n! ⇒ ∑
n! ≤ 1
đây chính là điều phải chứng minh.
Nhận xét 1. Bất đẳng thức LYM có thể dễ dàng suy ra từ định lý Bollobas, định lý 1.4 bằng cách, đặt
F = { A
1, A
2, . . . , A
m} và đặt B
i= [n] \ A
i. Khi đó điều kiện A
i∩ B
i= /0 thỏa mãn và điều kiện A
i∩ B
j6 = /0
trở thành A
i6⊆ A
j, tức là điều kiện của một phản xích. Chú ý là b
i= n − a
i. Đến đây thì
−1n
a
i+ b
i∑
n∑
m=
≤ 1.
a
ii=1Định lý 1.8. Một họ F các tập con của tập n phần tử X được gọi là không so sánh được nếu A, B là
hai phần tử bất kỳ của F thì A 6⊆ B.
Định lý 1.9 (Định lý Sperner). Cho F là một họ không so sánh được các tập con của tập n phần tử
X. Khi đó
| F | ≤ C [
n
2
]
n.
Chứng minh. Mặt khác, theo tính chất của nhị thức Newton thì hệ số trong khai triển (1 + x)
nthỏa tính
chất
n
<
< . . . <
.
nn−12
1
0
2Áp dụng vào ta có
k
jThay vào (*) ta có đánh giá
m. 1
≤ 1.
≤
n[
n
2
]
j=1kj