GT 4: Bassalygo, Erdős, và Sperner

4. Chặn dưới

Leonid Bassalygo là một học trò giỏi của người khổng lồ Kolmogorov. Từ những năm 1970, ông đã có nhiều đóng góp cơ bản trong lý thuyết thông tin, lý thuyết mã hóa, và lý thuyết các mạng chuyển mạch (switching networks). Có nhiều định lý và chặn mang tên ông. Ví dụ như chặn Elias-Bassalygo. Hiện nay ông là tổng biên tập tờ Problems in Information Transmission. Tạp chí tiếng Nga này có nội dung và tầm tương tự như tạp chí IEEE Transactions on Information Theory. Bài này sẽ thảo luận một chặn của Bassalygo cho đại lượng ${t(d,N)}$ , số hàng nhỏ nhất của một ma trận ${d}$ -phân-cách với ${N}$ cột.

Xét một ma trận ${d}$ -phân-cách ${{\bf M}=(m_{ij})}$ với ${t}$ hàng và ${N}$ cột. Nhớ rằng mỗi cột ${j}$ của ma trận có thể được đánh đồng với tập con ${\{ i \ | \ m_{ij} =1 \}}$ của tập ${[t] = \{1,\dots,t\}}$ . Bộ ${\mathcal F}$ gồm ${N}$ tập hợp này thỏa tính chất sau đây: lấy ${d+1}$ tập bất kỳ ${F_0, \dots, F_{d+1} \in \mathcal F}$ thì ta luôn có ${F_0 \not\subseteq F_1 \cup \cdots \cup F_d}$ . Tính chất này tiếng Anh gọi là tính chất ${d}$ -cover-free của bộ tập hợp ${\mathcal F}$ . (Dịch “ ${d}$ -cover-free” sang tiếng Việt thế nào nhỉ?) Hơn nữa, xét một tập ${F \in \mathcal F}$ bất kỳ với lực lượng ${|F| = w \leq d}$ , thì ${F}$ phải chứa một phần tử mà không tập nào khác có. Tại vì, nếu mỗi phần tử của ${F}$ đều thuộc một tập khác thì ${F}$ sẽ nằm trong hội của nhiều nhất ${w \leq d}$ tập khác, mẫu thuẫn với tính chất ${d}$ -phân-cách. Phần tử chỉ riêng ${F}$ có gọi là phần tử riêng của ${F}$ . Tổng quát hơn, một tập con chỉ chứa trong ${F}$ gọi là một tập con riêng của ${F}$ .

Do chỉ có tổng cộng ${t}$ phần tử, sẽ chỉ có nhiều nhất là ${t}$ phần tử riêng, và vì thế nhiều nhất là ${t}$ thành viên của ${\mathcal F}$ với lực lượng ${\leq d}$ . Cụ thể hơn, gọi ${n(w)}$ là số tập với lực lượng ${w}$ , thì ta có

$\displaystyle \sum_{w \leq d} n(w) \leq t. \ \ \ \ \ (1)$

Lại xét một tập ${F \in \mathcal F}$ với lực lượng ${w}$ . Nếu ta xóa khỏi ${{\bf M}}$ tất cả các hàng tương ứng với phần tử của ${F}$ và xóa luôn cả cột ${F}$ thì ta còn một ma trận ${{\bf M'}}$ với ${t-w}$ hàng và ${N-1}$ cột. Ma trận này phải có tính chất ${(d-1)}$ -phân-cách. Do đó,

$\displaystyle t - w \geq t(d-1,N-1). \ \ \ \ \ (2)$

Từ hai bất đẳng thức (1) và (2) chúng ta dễ dàng chứng minh chặn Bassalygo, chặn dưới cơ bản nhất cho ${t(d,N)}$ .

Định lý 1 (Chặn Bassalygo) Gọi ${t(d,N)}$ là số hàng nhỏ nhất của một ma trận ${d}$ -phân-cách với ${N}$ cột, ta có
$\displaystyle t(d,N) \geq \min\left\{ \binom{d+2}{2}, N \right\}. \ \ \ \ \ (3)$

Như vậy, nếu ${d}$ quá lớn (thỏa ${(d+1)(d+2) \geq 2N}$ ) thì thử nhóm không tốt hơn thử từng mẫu đơn lẻ một.

Chứng minh: Ta chứng minh (3) bằng qui nạp theo ${d}$ . Nhớ rằng ${d\leq N}$ . Dễ thấy rằng ${t(1,N) \geq \min\{3, N\}}$ . Gọi ${w_{\max}}$ là lực lượng lớn nhất trong ${N}$ tập của ${\mathcal F}$ . Nếu ${w_{\max} \leq d}$ thì bất đẳng thức (1) cho

$\displaystyle t \geq \sum_{w} n(w) = N.$

Nếu ${w_{\max} \geq d+1}$ thì từ bất đẳng thức (2) và giả thiết quy nạp ta có

$\displaystyle t \geq d+1+\min\left\{ \binom{d+1}{2}, N-1 \right\} \geq \min\left\{ \binom{d+2}{2}, N \right\}.$

$\Box$

Có một cách hơi khác để chứng minh chặn Bassalygo, từ một bài báo quan trọng hồi 1985 của Erdős-Frankl-Füredi.

Cố định một số nguyên dương ${w \leq t}$ . Trong họ ${\mathcal F}$ gồm ${N}$ tập hợp, gọi ${\mathcal F_w}$ là tập tất cả cả tập trong ${\mathcal F}$ có một tập con riêng gồm ${w}$ phần tử. Nghĩa là ${\mathcal F_w}$ bao gồm tất cả các thành viên ${F}$ của ${\mathcal F}$ sao cho ${F}$ chứa một tập con ${S}$ với lực lượng ${w}$ và không có bất kỳ thành viên nào khác của ${\mathcal F}$ chứa ${S}$ .

Bổ đề 2 (Bổ đề Erdős-Frankl-Füredi) Nếu ${F \in \mathcal F - \mathcal F_w}$ và ${F_1, \cdots, F_i \in \mathcal F}$ thì
$\displaystyle \left| F \setminus \bigcup_{j=1}^i F_j \right| \geq (d-i)w + 1.$

Do đó, nếu có ${d+1}$ tập khác nhau ${F_0, \cdots, F_d \in \mathcal F - \mathcal F_w}$ thì
$\displaystyle \left| \bigcup_{i=0}^d F_i \right| \geq \frac 1 2 (d+1)(dw+2).$

Bài tập 1 Chứng minh bổ đề Erdős-Frankl-Füredi. Gợi ý: để chứng minh phần “do đó”, dùng đẳng thức sau đây
$\displaystyle \left|\bigcup_{i=0}^d F_i \right| = |F_d| + |F_{d-1} \setminus F_d| + \cdots + \left|F_0 \setminus \bigcup_{j=1}^d F_j \right|.$

Từ bổ để Erdős-Frankl-Füredi, chúng ta chứng minh chặn Bassalygo như sau. Nếu ${\mathcal F}$ chứa một tập ${F}$ với một phần tử riêng ${x}$ nào đó, thì — sau khi xóa hàng ${x}$ và cột ${F}$ ra khỏi ${{\bf M}}$ — ma trận kết quả cho ta một bộ tập hợp ${\mathcal F'}$ vẫn thỏa tính chất ${d}$ -cover-free. Theo quy nạp

$\displaystyle t \geq 1 + \min\left\{\binom{d+2}{2}, N-1\right\} \geq \min\left\{\binom{d+2}{2}, N\right\}.$

(Trường hợp cơ bản của phép qui nạp là khi ${N =d}$ , hiển nhiên đúng. Do đó ta xét ${N \geq d+1}$ .) Nếu không tồn tại tập hợp có phần tử riêng, nghĩa là ${\mathcal F_1 = \emptyset}$ thì theo bổ đề Erdős-Frankl-Füredi, xét ${d+1}$ tập ${F_0, \cdots, F_d \in \mathcal F}$ ta có

$\displaystyle t \geq \left|\bigcup_{i=0}^d F_i \right| \geq \binom{d+2}{2}.$

Không những thế, bổ đề Erdős-Frankl-Füredi còn giúp chúng ta chứng minh chặn dưới tốt nhất hiện có cho hàm ${t(d,N)}$ là ${t(d,N) = \Omega\left(\frac{d^2}{\log d}\log N \right)}$ . Nhưng trước hết, ta chứng minh một bổ đề cổ điển của Sperner.

Bổ đề 3 (Bổ đề Sperner) Có nhiều nhất ${\binom{t}{\lceil t/2 \rceil}}$ các tập con của ${[t]}$ sao cho không có tập con nào chứa tập con nào. (Họ tập con như vậy gọi là một phản-chuỗi (anti-chain) của Boolean lattice tương ứng với ${[t]}$ .)

Chứng minh: Ta dùng phương pháp định trị một đại lượng bằng hai cách. (Cái mẹo đếm chuỗi sau đây rất phổ dụng trong extremal set theory, xem thêm hai quyển Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability và Sperner Theory.) Gọi ${\mathcal F}$ là một họ phản chuỗi của ${[t]}$ . Xét một chuỗi tập hợp ${(C_1, \dots, C_t)}$ trong đó ${C_i \subset [t]}$ , ${C_i \subset C_{i+1}}$ , và ${|C_i| = i}$ . Có tổng cộng ${t!}$ chuỗi như thế. Không có hai thành viên của ${\mathcal F}$ nằm trong cùng chuỗi. Một thành viên ${F \in \mathcal F}$ với ${|F|=k}$ nằm trong ${k!(t-k)!}$ chuỗi. Do đó

$\displaystyle t! \geq \sum_{F \in \mathcal F, \ |F|=k} k!(t-k)!$

Suy ra

$\displaystyle 1 \geq \sum_{F \in \mathcal F} \frac{1}{\binom{t}{|F|}}.$

Mà với mọi ${k}$ thì ${\binom t k \leq \binom{t}{\lceil t/2 \rceil}}$ . Ta kết luận rằng

$\displaystyle 1 \geq \sum_{F \in \mathcal F} \frac{1}{\binom{t}{\lceil t/2 \rceil}} = |\mathcal F|/\binom{t}{\lceil t/2 \rceil}.$

$\Box$

Định lý 4 (Định lý Erdős-Frankl-Füredi) Gọi ${\mathcal F}$ là một họ ${d}$ -cover-free bất kỳ gồm ${N}$ thành viên trên tập ${[t]}$ . Khi ${d\geq 2}$ ta có
$\displaystyle N = |\mathcal F| \leq d + \binom{t}{\left\lceil \frac{t-d}{\binom{d+1}{2}} \right\rceil}.$

Nếu ${d=1}$ ta có
$\displaystyle N = |\mathcal F| \leq \binom{t}{\lceil t/2 \rceil}.$

Chứng minh: Trường hợp ${d=1}$ chính là nội dung bổ đề Sperner. Xét ${d\geq 2}$ . Cố định ${w \leq t/2}$ . Xét bộ tập hợp ${\mathcal F}$ , và ${\mathcal F_w \subseteq \mathcal F}$ như trên. Gọi ${\mathcal F_{<w}}$ là bộ tất cả các tập trong ${\mathcal F}$ với lực lượng nhỏ hơn hẳn ${w}$ . Để chứng minh định lý này, ta chứng minh hai bất đẳng thức sau đây là đủ:

$\displaystyle |\mathcal F_w| + |\mathcal F_{<w}| \leq \binom t w \ \ \ \ \ (4)$

và

$\displaystyle |\mathcal F - \mathcal F_w \cup \mathcal F_{<w}| \leq d, \text{ khi } w = \left\lceil \frac{t-d}{\binom{d+1}{2}} \right\rceil. \ \ \ \ \ (5)$

Gọi ${\mathcal A}$ là bộ các tập con riêng với lực lượng ${w}$ của các thành viên trong ${\mathcal F_w}$ . Gọi ${\mathcal B}$ là bộ các tập con của ${[t]}$ thỏa tính chất sau: mỗi tập ${B\in \mathcal B}$ có lực lượng ${w}$ , và ${B}$ chứa một thành viên nào đó của ${\mathcal F_{<w}}$ . Dễ thấy ${\mathcal A}$ và ${\mathcal B}$ không giao nhau, ${|\mathcal F_w| \leq |\mathcal A|}$ , và ${|\mathcal A| + |\mathcal B| \leq \binom n w}$ . Do đó, nếu ta chứng minh được rằng ${|\mathcal F_{<w}| \leq |\mathcal B|}$ thì (4) đúng. Để chứng minh điều này, ta lại dùng mẹo đếm chuỗi trong chứng minh bổ để Sperner.

Xét một chuỗi tập hợp ${(C_1, \dots, C_w)}$ trong đó ${C_i \subset [t]}$ , ${C_i \subset C_{i+1}}$ , và ${|C_i| = i}$ . Do tính ${d}$ -cover-free, không thể có hai thành viên của ${\mathcal F_{<w}}$ nằm trong cùng một chuỗi như vậy. Ngoài ra, xét ${F \in \mathcal F_{<w}}$ tùy ý, ${|F|=k}$ , thì tổng số chuỗi chứa ${F}$ là ${k! \binom{t-k}{w-k} (w-k)!}$ . Mỗi chuỗi chứa ${F}$ đều phải kết thúc bằng một thành viên của ${\mathcal B}$ . Tổng số chuỗi kết thúc bằng một thành viên cụ thể của ${\mathcal B}$ là ${w!}$ . Do đó,

$\displaystyle |\mathcal B|w! \geq \sum_{F \in \mathcal F_{<w}, |F|=k} k! \binom{t-k}{w-k}(w-k)!.$

Do ${w \leq t/2}$ , ta có ${\binom{t-k}{w-k} \geq \binom{w}{w-k}}$ , và vì thế

$\displaystyle |\mathcal B| \geq \sum_{F \in \mathcal F_{<w}, |F|=k} \frac{\binom{t-k}{w-k}}{\binom{w}{w-k}} \geq |\mathcal F_{<w}|.$

Cuối cùng, ta chứng minh (5). Giả sử ${|\mathcal F - \mathcal F_w \cup \mathcal F_{<w}| \geq d+1}$ thì tồn tại ${d+1}$ thành viên khác nhau trong bộ ${\mathcal F - \mathcal F_w}$ . Bổ đề Erdös-Frankl-Füredi cho ta biết ${t \geq \frac 1 2(d+1)(dw+2)}$ . Nhưng, khi ${w = \left\lceil \frac{t-d}{\binom{d+1}{2}} \right\rceil}$ thì điều này không thể xảy ra. $\Box$