Một số định lý trong lý thuyết tập hợp cực trị

Một số định lý trong lý thuyết tập hợp cực trị
Vũ Thế Khôi, email: vtkhoi@math.ac.vn
Viện Toán Học, 18 Hoàng Quốc Việt, Hà Nội
1 Giới thiệu
Những bài toán trong lý thuyết tập hợp cực trị thường có dạng: cho một
tập (hay 1 họ các tập) S thỏa mãn một số điều kiện cho trước, tìm max
hoặc min của |S|. Khi nào dấu đẳng thức xảy ra?
Ta xét một bài tập đơn giản
Bài toán 1. Cho F là một họ các tập con của một tập n phần tử X. Giả sử
bất kỳ hai phần tử nào của F cũng có giao khác rỗng. Hỏi giá trị lớn nhất
có thể của |F| là bao nhiêu?
Bài toán 1’. Cho F là một họ các tập con của một tập n phần tử X. Giả
sử bất kỳ hai phần tử A,B nào của F cũng có A∪B 6= X . giá trị lớn nhất
có thể của |F| là bao nhiêu?
Bài toán 2. Cho F là một họ các tập con của một tập n phần tử X. Giả
sử bất kỳ hai phần tử A,B nào của F cũng có A ∩ B 6= ∅ và A ∪ B 6= X .
giá trị lớn nhất có thể của |F| là bao nhiêu?
2 Các định lý cơ bản
Ta gọi một tập có k phần tử là k-tập. Một họ F các tập con của một n-tập
được gọi là họ giao nếu với mọi A,B ∈ F ta có A ∩B 6= ∅.
Định lý Erdo¨s-Ko-Rado. Một họ giao F các k-tập con của một n-tập
X(k ≤ n/2) có không quá (n−1k−1) phần tử.
Chứng minh. Đặt X := {0, 1, 2, . . . , n − 1}. Với s ∈ X, ký hiệu Bs :=
{s, s + 1, . . . , s+ k − 1}. trong đó các số mod n.
1
Ta nhận thấy trong số các tập Bs, Có không quá k tập nằm trong F . Thật
vậy, giả sửB0 ∈ F . Như vậy có đúng 2k−2 tập khác làBi,−(k−1) ≤ i ≤ k−1
có giao khác rỗng với B0. Tuy nhiên các cặp Bi và Bi+k lại rời nhau nên
ngoài B0 ra, F chỉ chứa nhiều nhất là k − 1 tập Bs.
Với σ là một hoán vị của X, ta đặt σ(Bs) := {σ(s), σ(s + 1), . . . , σ(s +
k − 1)}, ký hiệu L := {(σ, s)|σ(Bs) ∈ F}. Từ nhận xét ngay trên ta có
|L| ≤ k(n!). Mặt khác với mỗi s và phần tử A ∈ F cố định, có đúng
k!(n − k)! hoán vị σ mà σ(Bs) = A. Do đó |L| = n|F|k!(n − k)!. Như vậy
|F| ≤ kn!
nk!(n− k)! =
(
n− 1
k − 1
)
.
Định lý Sperner. Cho F là một họ các tập con của một n-tập X thỏa
mãn A * B với mọi A,B ∈ F . Ta có |F| ≤ ( nbn
2
c
)
.
Chứng minh Ta nhận thấy số các dãy tăng các tập con
M1 ⊂M2 ⊂ · · · ⊂Mn−1 ⊂Mn = X với |Mi| = i đúng bằng n!.
Nếu A là một r-tập thì số các dãy tăng các tập con
M1 ⊂ · · · ⊂Mr−1 ⊂ A ⊂Mr+1 ⊂ · · · ⊂Mn = X với |Mi| = i đúng bằng
r!(n− r)!.
Ta nhận thấy nếu A,B ∈ F thì tập các dãy tăng chứa A và tập các dãy
tăng chứa B là rời nhau. Như vậy nếu F = {A1, A2, . . . , Ap} với |Ai| = ni
thì ta có :
p∑
i=1
ni!(n − ni)! ≤ n!.
Như vậy
p( n
bn
2
c
) ≤
p∑
i=1
1( n
ni
) ≤ 1.
Với F là họ tất cả các bn
2
c-tập con thì hiển nhiên đẳng thức xảy ra.
Từ chứng minh trên ta nhận được ngay hệ quả sau.
Hệ quả.(Bất đẳng thức Lubell-Yamamoto-Meshalkin) Cho F là một họ
các tập con của một n-tập X thỏa mãn A * B với mọi A,B ∈ F . Gọi ak là
2
số các k-tập con thuộc F . Khi đó
n∑
k=0
ak(n
k
) ≤ 1.
Định lý De Bruijn Erdo¨s. Cho F là một họ các tập con của một
n-tập X thỏa mãn:
i) |F| ≥ 2, và |A| ≥ 2,∀A ∈ F .
ii) Với 2 phần tử bất kỳ x, y ∈ X tồn tại duy nhất A ∈ F với x, y ∈ A.
Khi đó |F| ≥ n.
Chứng minh. Đặt |F| = m và rx := |{A ∈ F|x ∈ A}| với x ∈ X. Nếu
x /∈ A, dễ thấy rx ≥ |A| vì bất kỳ y ∈ A cũng có một tập B chứa x và y.
Giả sử m ≤ n, khi đó ta có m(n− |A|) ≥ n(m− rx) với mọi x ∈ A. Ta có
1 =
∑
A∈F
∑
x/∈A
1
m(n− |A|) ≤
∑
x∈X
∑
A:x/∈A
1
n(m− rx) = 1.
Do đó dấu đẳng thức xảy ra ở mọi chỗ, tức là ta có m ≥ n và nếu m = n
thì |A ∩B| = 1,∀A,B ∈ F .
3 Một số bài tập về tập hợp
♦ Cho k ≥ 1 là một số tự nhiên. Tìm số tự nhiên nhỏ nhất n sao cho với
mọi tập gồm n số nguyên luôn có 2 số mà tổng hoặc hiệu của chúng chia
hết cho 2k + 1.
Gợi ý: tập {k + 1, . . . , 2k + 1} không thỏa mãn tính chất của bài toán,
vậy n > k + 1. Ta chứng tỏ n = k + 2. Với một tập A bất kỳ gồm k + 2 số,
xét tập A′ các phần dư mod 2k + 1 của A như một tập con của {−k,−k +
1, . . . , 0, 1, · · · , k}. Nếu |A′| = k+ 2 thì luôn có hai phần tử có tổng bằng 0.
♦ Cho (Ai)ni=1, (Bj)nj=1, (Ck)nk=1 là ba phân hoạch của một tập hữu hạn X.
giả sử với mọi bộ ba số (i, j, k) ta có :
|Ai ∩Bj|+ |Bj ∩ Ck|+ |Ck ∩Bi| ≥ n.
3
Chứng tỏ rằng |X| ≥ n3/3. Với |X| = n3/3, hãy chỉ ra các phân hoạch để
dấu đẳng thức xảy ra.
Gợi ý: Cộng tất cả các BĐT, ta được điều cần cm. Nếu |X| = n3/3, viết
X = E11 ∪ E12 ∪ . . . ∪ E1n ∪ E21 ∪ E22 ∪ . . . ∪ E2n ∪ . . . ∪ En1 ∪ En2 ∪ . . . ∪Enn .
với |Eji | = n/3,∀i, j. Đặt Ai := ∪nj=1Aij , Bj := ∪ni=1Aij, Ck := ∪ni=1Aik+i−1≡n
ta được các phân hoạch mà dấu đẳng thức xảy ra.
♦ Xác định số n lớn nhất sao cho tồn tại các tập phân biệt S1, S2, . . . , Sn
thỏa mãn:
i) |Si ∪ Sj| ≤ 2006 với mọi 1 ≤ i, j ≤ n.
ii) Si ∪ Sj ∪ Sk = {1, 2, . . . , 2010} với mọi 1 ≤ i < j < k ≤ n.
Gợi ý: Đặt G{i,j} := {1, 2, . . . , 2010} \ (Si ∪ Sj) với 1 ≤ i, j ≤ n. Từ (i)
ta có |G{i,j}| ≥ 4 còn từ (ii) ta có G{i,j} ∩ G{k,l} = ∅ nếu i 6= j, k 6= l và
{i, j} 6= {k, l}. Từ đó ta có
2010 ≥ | ∪1≤i<j≤n G{i,j}| =
∑
1≤i<j≤n
|G{i,j}| ≥ 4
(
n
2
)
.
Do đó n ≤ 32.
Ví dụ với n = 32 xây dựng như sau: chia tập {1, 2, . . . , 1984} thành 496
4-tập rời nhau G{i,j}, 1 ≤ i < j ≤ 32. Xác định tập Si := {1, 2, . . . , 2010} \
∪j 6=iG{i,j} thỏa mãn các điều kiện (i) và (ii).
♦ Cho Dk, 0 ≤ k ≤ n − 1 là tập gồm các tập con của {1, 2, . . . , n} sao cho
với bất kỳ A,B ∈ Dk ta có |A ∩B| ≤ k. Chứng minh rằng
|Dk| ≤
(
n
0
)
+
(
n
1
)
+
(
n
2
)
+ · · · +
(
n
k + 1
)
.
Gợi ý: gọi Pk là tập gồm các tập con của {1, 2, . . . , n} chứa không quá
k phần tử. Bất kỳ tập Dk cực đại nào cũng chứa Pk. Với A ∈ Dk \ Pk đặt
A˜ := {A1, A2, . . . , As|Ai ⊆ A, |Ai| = k + 1}. Như vậy họ (A˜)A∈Dk\Pk gồm
toàn các tập rời nhau. Vậy |Dk \ Pk| ≤ |Pk+1 \ Pk| hay |Dk| ≤ |Pk+1|.
♦ (Chọn đội tuyển Romania 1999) Cho A là một tập có n phần tử. Giả sử
A1, A2, . . . , Am là các tập con thỏa mãn |Ai| = 3,∀i và |Ai∩Aj | ≤ 1,∀i 6= j.
4
Chứng minh rằng tồn tại một tập con X của A không chứa bất kỳ tập Ai
nào và |X| ≥ b√2nc.
Gợi ý: giả sử X là một tập con tối đại thỏa mãn đầu bài. Khi đó với
mỗi u ∈ A \X sẽ có 2 phần tử x1, x2 ∈ X sao cho tập {u, x1, x2} trùng với
một tập Ai nào đó. Theo đầu bài thì đây là một đơn ánh từ A \X đến tập
gồm các 2-tập của X. Vậy ta có
n− |X| ≤ |X|(|X| − 1)/2.
Từ đây ta có điều cần chứng minh.
♦ Giả sử X là một tập hữu hạn và Ei, 1 ≤ i ≤ m là các tập con thỏa mãn
|Ei| ≥ 2,∀i và |Ei ∩ Ej | 6= 1,∀i, j. Chứng minh rằng có thể tô tập X bằng
hai mầu sao cho mỗi tập Ei đều chứa các phần tử được tô cả hai mầu.
Gợi ý: ĐặtX = {x1, x2, . . . , xn}.Giả sử ta đã tô màuXk := {x1, x2, . . . , xk}
bằng hai màu xanh và đỏ thỏa mãn đầu bài nhưng nếu thêm xk+1 thì
không tô được nữa. Khi đó tồn tại tập Ej , El chứa xk+1 và Ej, El ⊆
{x1, x2, . . . , xk+1} sao cho Ej ∩ Xk gồm toàn các màu xanh, El ∩ Xk gồm
toàn các màu đỏ. Như vậy |Ej ∩ El| = 1 mâu thuẫn với giả thuyết.
♦ (Bollobas) Cho F = {A1, A2, . . . , Am} là một họ giao các tập con của một
n-tập X với |Ai| = ni ≤ n/2. Chứng minh rằng
m∑
k=1
1(n−1
ni−1
) ≤ 1.
Gợi ý: Tương tự như trong chứng minh định lý Erdos-Ko-Rado, ta đặt
gọi L là tập các bộ (σ, s, i) mà Ai = {σ(s), σ(s + 1), . . . , σ(s + ni − 1)}. Ta
nhận được bất đẳng thức khi đếm các phần tử của L với trọng của (σ, s, i)
là 1ni .
♦ Cho F là một họ các tập con của X với |F| = m. Chứng tỏ rằng trong
số những tập có dạng (A \B)∪ (B \A) với A,B ∈ F có ít nhất m tập phân
biệt.
Gợi ý: Ánh xạ f(S) = (A \ S) ∪ (S \A) là 1− 1.
5
♦ (Bulgari 2004) Cho A1, A2, . . . , An là các tập hữu hạn thỏa mãn |Ai ∩
Ai+1| > n−2n−1 |Ai+1| với i = 1, 2, . . . , n (An+1 ≡ A1). Chứng minh rằng
∩ni=1Ai 6= ∅.
Gợi ý: Giả sử |A1 là lớn nhất. Ký hiệu Bi := Ai ∩Ai+1. Ta có :
|An| ≥ |Bn−1 ∪Bn| > n− 2
n− 1 |An|+
n− 2
n− 1 |A1| − |Bn−1 ∩Bn|.
Do đó |An−1 ∩ An ∩ A1| = |Bn−1 ∩ Bn| > n−3n−1 |A1|. Từ đó chứng minh quy
nạp rằng :
|An−k ∩An−k+1 ∩ · · · ∩A1| > n− k − 2
n− 1 |A1|.
Với k = n− 2 ta có điều cần chứng minh
♦ (Iran 1999) Giả sử X = {1, 2, . . . , n} và A1, A2, . . . , Ak là các tập con của
X sao cho với mọi 1 ≤ i1, i2, i3, i4 ≤ n ta có:
|Ai1 ∪Ai2 ∪Ai3 ∪Ai4 | ≤ n− 2.
Chứng minh rằng k ≤ 2n−2.
Gợi ý: Gọi A là tập có |A| nhỏ nhất trong số các tập thỏa mãn A * Ai ∪Aj
với i, j nào đó (không nhất thiết phân biệt). Dễ dàng chứng minh được họ
các tập S1 := {A ∩ A1, A ∩ A2, . . . , A ∩ Ak} chứa không quá 2|A|−1 phần
tử vì nếu M ∈ S1 thì A \ M /∈ S1. Tương tự ta chứng minh được tập
S2 := {B ∩ A1, B ∩ A2, . . . , B ∩ Ak}, với B = X \ A, có không quá 2|B|−1
phần tử vì nếu M ∈ S2 thì B \M /∈ S2 (trái lại thì B ⊆ Ak ∪Al, mặt khác
ta có A \m ⊆ Ai ∪Aj dẫn đến mâu thuẫn |Ai ∪Aj ∪Ak ∪Al| ≥ n− 1).
♦ Cho 35 tập A1, A2, . . . , A35 mỗi tập có 27 phần tử. Biết rằng các tập này
thỏa mãn |Ai ∩Aj ∩Ak| = 1 với mọi 1 ≤ 1 < j < k ≤ 35. Chứng minh rằng
∩35i=1Ai 6= ∅.
Gợi ý: Nếu ∃x ∈ A1 sao cho ∩35i=1Ai = {x} thì bài toán đúng. Trái lại,
xét họ các tập Bx := {Ai| x ∈ Ai}x∈A1,i=2,3,...,35 sao cho |Bx| ≥ 2. Đây
là một họ các tập con của tập A2, A3, . . . , A35 mâu thuẫn với định lý De
Bruijn-Erdo¨s.
6
♦ (Putnam 1980) Cho A1, A2, . . . , A1066 là các tập con khác nhau của một
tập hữu hạn X thỏa mãn |Ai| > |X|/2,∀i. Chứng tỏ rằng tồn tại 10 phần
tử của X sao cho mỗi tập Ai, 1 ≤ i ≤ 1066 chứa ít nhất một phần tử này.
Gợi ý: Từ giả thiết ta nhận thấy tồn tại x1 ∈ X nằm trong nhiều hơn 533
tập Ai. Gọi B1, B2, . . . , Bs, s ≤ 532 là các tập không chứa x1. Ta đưa bài
toán về bài toán tương tự với tập Y = X \{x1} và họ các tập B1, B2, . . . , Bs.
Lập luận tương tự ta tìm được x2 nằm trong nhiều hơn s/2 tập và lại đưa bài
toán về trường hợp Z = X \ {x1, x2} và họ các tập B1, B2, . . . , Bt, t ≤ 265.
Cư tiếp tục đến phần tử x10 thì nhận được dãy cần tìm.
7