MỘT SỐ ĐỊNH LÝ QUAN TRỌNGĐỊNH NGHĨA CHO F LÀ MỘT HỌ CÁC TẬP HỢ...

1. MỘT SỐ ĐỊNH LÝ QUAN TRỌNG

Định nghĩa 1.1. Cho F là một họ các tập hợp con của một tập n phần tử X . Khi đó F được gọi là họ

giao nếu với mọi A, B ∈ F ta có A ^T B 6 = /0.

Định lý 1.2. Cho F là một họ giao của một tập n phần tử X . Khi đó | F | ≤ 2

.

Chứng minh. Lấy một tập con A ⊆ X. Khi đó với mỗi cặp tập con (A, X \ A) của X , thì nhiều nhất là

một trong hai tập A hoặc X \ A thuộc vào F (vì nếu cả hai tập A, X \ A đều thuộc vào F thì do

A ∩ (X \ A) = /0

mâu thuẫn với F là một họ giao các tập con của X). Vì X có 2

tập con, và mỗi cặp tập con (A, X \ A)

có nhiều nhất một tập thuộc F . Do đó

| F | ≤ 1

2 · 2

= 2

.

Định lý 1.3 (Định lý Erdos-Ko-Rado). Một họ F các k_tập (một tập hợp có k phần tử gọi là k_tập)

của một tập n phần tử X (k ≤ n