Home > Combinatorics > Định lý Hall và SDRs

Định lý Hall và SDRs


Bài toán mở đầu của chúng ta là:

Cho n chàng trai, nếu một nhóm k chàng trai bất kì quen với ít nhất k cô gái (1\le k\le n). Chứng tỏ rằng đây là điều kiện cần và đủ để tổ chức một đám cưới tập thể sao cho mỗi chàng trai cưới một cô gái mình quen

 

Có thể mô hình lại bài toán bằng tập hợp. Gọi A_i, \ \ i=1,2,..,n là tập các cô gái mà chàng trai thứ i quen. Khi đó với mọi i_1,i_2,...,i_k \in\{1,2,...,n\} thỏa mãn

 

|A_{i_1}\cup A_{i_2}\cup...\cup A_{i_k}|\ge k (Điều kiện Hall)

 

khi và chỉ khi tồn tại (a_1,...,a_n)\in A_1\times A_2 \times ...\times A_n sao cho a_i\neq a_j với i\neq j

 

Đây là cũng là nội dung của định lý Hall (Định lý này được phát biểu bởi Philip Hall năm 1935, và nó được biết đến đầy đủ với chứng minh và các kết quả của Marshall Hall năm 1948) còn gọi là định lý Đám cưới (Hall’s Marriage Theorem)

 

Một bộ (a_1,...,a_n) như vậy gọi là một hệ đại diện phân biệt cho hệ tập hợp (A_1,A_2,...,A_n) (system of distinct representatives, viết tắt là SDR), phần tử a_i\in A_i gọi là đại diện cho A_i, lưu ý rằng a_i\neq a_j với i\neq j. Như vậy nếu như hệ tập (A_1,...,A_n) thỏa mãn điều kiện Hall thì tồn tại một SDR cho hệ đó và điều ngược lại nếu một hệ có SDR thì nó thỏa mãn điều kiện Hall. Một SDR nếu có nói chung là không duy nhất, bài toán cần quan tâm là có bao nhiêu SDR của một hệ tập hợp cho trước.

 

Cho A=(a_{ij})_n, kí hiệu perA=\sum_{\sigma\in S_n}a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)}

 

Xét họ các tập A_1, A_2,..., A_n là các tập con của [n]. Ma trận liên thuộc của hệ này là A=(a_{ij}) được xác định như sau:

a_{ij}=\left\{\begin{array}{ll}1, \ \ \ \ i \in A_j\\ 0, \ \ \ \ i \notin A_j \end{array}\right.

 

Rõ ràng perA chính bằng số SDR của họ A_1, A_2,...,A_n do a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)} bằng 1 khi và chỉ khi \sigma(i)\in A_i với mọi i tức là \{\sigma(1), \sigma(2),...,\sigma(n)\} là SDR của A_1, A_2,...,A_n.

 

Trong phần đầu tiên, ta sẽ bàn tới chứng minh của định lý Hall. Phần tiếp theo sẽ nói đến một số vấn đề tổ hợp được phát triển liên quan đến các SDR.

 

A – Chứng minh Định lý Hall.

 

I. Lời giải thứ nhất.

 

Để đơn giản ta viết A_I thay cho \bigcup_{i\in I}A_i. Điều kiện Hall viết lại như sau:

 

                               với mọi

 

+ Nếu hệ (A_i)_{ i\in E} có SDR, hiển nhiên Điều kiện Hall được thỏa mãn.

 

+ Ngược lại, giả sử Điều kiện Hall được thỏa mãn cho hệ (A_i)_{ i\in E}, chú ý là mọi hệ con (A_i)_{ i\in K} với K\subset E cũng thỏa mãn Điều kiện Hall. Ta chứng minh sự tồn tại SDR cho hệ này theo quy nạp theo số các tập trong hệ. Nếu hệ chỉ gồm 1 tập thì định lý là hiển nhiên. Giả sử định lý đúng với tất cả các trường hợp số các tập trong hệ bé hơn n.

 

Ta chia ra hai trường hợp:

 

1. Có một tập con I của E khác trống và khác E sao cho | A_I |=| I |.

 

Đặt là tập có số phần tử bé nhất như vậy.  Đặt A'_i=A_i\setminus A_J. Điều kiện Hall cũng thỏa mãn với hệ con nên theo giả thiết quy nạp, hệ này có SDR là  
 

Với tập ,  do Điều kiện Hall nên |A_{J\cup K}|\ge |J\cup K|.

 

Chú ý là |A'_K|=|A_{J\cup K}|-|A_J|, \ |A_J|=|J||K|=|J\cup K|-|J|. Suy ra |A'_K|\ge |K| tức là Điều kiện Hall thỏa mãn cho hệ (A'_i)_{i \in E\setminus J}

 

Tương tự cũng từ giả thiết quy nạp hệ (A'_i)_{i \in E\setminus J} có SDR là .
Khi đó (x_j)_{j\in J}\cup (x_j)_{j\in E\setminus J} là một SDR của hệ (A_i)_{i\in E}

 

2. Trường hợp ngược lại

 

Do Điều kiện Hall được thỏa mãn nên |A_i|\ge|\{i\}|=1, với i=1,2,...,n. Tồn tại x_n\in A_n.

 

Với j=1,2,...,n-1 đặt A'_j=A_j\setminus \{x_n\}. Xét  khác trống, thế thì:

 

| A'_J | \ge | A_J |-1 > | J |-1 (chú ý là không có dấu bằng do giả sử ban đầu) hay |A'_J|\ge |J|

 

Vậy hệ (A'_1,A'_2,...,A'_{n-1}) cũng thỏa mãn Điều kiện Hall. Theo nguyên lý quy nạp suy ra hệ này có SDR là (x_1,x_2,...,x_{n-1}). Và cuối cùng (x_1,x_2,...,x_{n-1},x_n) chính là SDR của (A_i)_{i\in E}.

 

Định lý được chứng minh hoàn toàn. 

 

Sau đây là một cách chứng minh khác ngắn ngọn, trực tiếp hơn:

 

II. Lời giải thứ hai. (Rado)

 

Giả sử hệ (A_1,...,A_n) thỏa mãn Điều kiện Hall. Ta bắt đầu bỏ đi phần tử thuộc mỗi tập A_i sao cho Điều kiện Hall vẫn được thỏa mãn. Cuối cùng thu được hệ tối giản  vẫn thỏa mãn Điều kiện Hall, với B_i\subset A_i, từ tối giản ở đây hiểu là nếu như bỏ đi một phần tử từ một tập B_i bất kì nào đó thì Điều kiện Hall không còn được thỏa mãn.

 

Ta chứng minh rằng .  Thật vậy, không mất tính tổng quát giả sử B_1 có chứa phần tử khác nhau là x,y. Do nếu bỏ đi x hoặc y thì điều kiện Hall không còn thỏa mãn nên có hai tập chỉ số   sao cho:

 

Với X=(B_1\setminus\{x\})\cup\bigcup_{i\in P}B_i, Y=(B_1\setminus\{y\})\cup\bigcup_{i\in P}B_i thì |X|\le |P||Y|\le |Q|

 

Mặc khác

 

X\cup Y=B_1\cup ( \bigcup_{i\in P\cap Q}B_i )

 

và 

 

 

 

Từ Điều kiện Hall suy ra |X\cup Y|\ge 1+|P\cup Q| và   

 

Áp dụng Nguyên lý bao hàm loại trừ và nhận xét trên thì

|P|+|Q|\ge |X|+|Y|=|X\cap Y|+|X\cup Y|\ge 1+|P\cap Q|+|P\cup Q|=1+|P|+|Q|

 

Điều vô lý này dẫn đến khẳng định |B_i|=1, i=1,2,...,n.

 

Các tập B_i như vậy phải đôi một không giao nhau, vì ngược lại nếu có  sao cho B_i=B_j=\{x\} thì hợp của hai tập này B_i\cup B_j=\{x\} có số phần tử là 1, trái với điều kiện Hall.

 

Như vậy chọn được x_i\in B_i\subset A_i, \ i=1,2,...,n , sao cho x_i\neq x_j để lập thành SDR của hệ (A_1,...,A_n)

 

III. Lời giải thứ ba

 

Có lẽ lời giải thứ hai ở trên là sáng sủa nhất. Đã có rất nhiều lời giải cho định lý thú vị này mà cho đến nay nó vẫn là một chủ đề rất cuốn hút. Cách đây mấy năm có một lời giải mới của một sinh viên và 1 giảng viên người Trung Quốc khá độc đáo và sáng tạo. Xin trình bày lại trên ý tưởng của Hui-Qin và Zhi-Wei, ĐH Najing.

 

Định lý 1. A_1, A_2,...,A_n, \ n>1 là tập con của tập X. Giả sử (a_i)_{i=1}^{n-1} là SDR của ( A_i )_{ i=1 }^{ n-1 } . Với J\subset\{1,2,...,n\} có chứa phần tử n thì có đúng |\bigcup_{j\in J}A_j|-|J|+1 cách chọn phần tử a\in X để hợp với a_1,a_2,a_{n-1} và sắp lại để tạo thành một SDR (a'_1,...,a'_n) của (A_i)_{i=1}^{n}, với a'_i đại diện cho A_i, \ i\notin J.

 

Xét một graph  với các đỉnh đánh số là 1,2,...,n sao cho  (đỉnh   kề với ) nếu và chỉ nếu . Đặt 
 

J=\{j\in\{1,2,...,n\} \ | \ tồn tại một đường đi từ j đến n \} A=\bigcup_{j\in J}A_j

 

Như vậy ta có nhận xét: a_i\in A khi và chỉ khi tồn tại j\in J để a_i\in A_j hay tồn tại j\in J để (i,j)\in E, điều này cũng tương đương với tồn tại một đường đi từ i đến n hay i\in J.

 

Suy ra \{ i\in \{1,2,...,n-1\} \ | \ a_i\in A\}=J\setminus\{n\}

 

Đặt B=A\setminus\{a_i \ | \ i\in J\setminus\{n\} \ \}. Hiển nhiên B\cap\{a_1,...,a_{n-1}\}=\emptyset|B|=|A|-|J|+1

 

Xét $latex a\in  X $ sao cho \{ a \} \cup \{ a_1, ... , a_{n-1} \} = ( a'_1 , ... ,a'_n ) là một SDR của (A_i)_{i=1}^{n} với  đại diện cho A_i, \ i\notin J. Rõ ràng thì a\in Ba đại diện cho A_j nào đó với j\in J

 

Mặt khác:

 

– Nếu thì tồn tại sao cho . Nếu thì đặt tạo thành thỏa mãn yêu cầu.

 

– Nếu thì tồn tại một đường đi từ đỉnh j đến n, đặt đường đi đó là , với . Chú ý là . Ta đặt , hiển nhiên với mọi . Nếu ta đặt , khi đó là SDR thỏa mãn điều kiện bài toán.

 

Vậy định lý đã được chứng minh.

 

Điều thú vị suy ra từ mệnh đề này là với bất kì một SDR nào đó của hệ thì có tối thiểu cách để mở rộng thành một SDR của hệ . Ở đây :

 

                                             

 

Như vậy định lý Hall chỉ là hệ quả của đánh giá tuyệt đẹp trên!

 

IV. Các hệ quả.

 

Các định lý sau là hệ quả của định lý Hall cũng có nhiều ứng dụng quan trọng

 

Định lý 2. Xét hệ các tập con của tập . Nếu như:

 

i/ |A_i|=m, \ i=1,2,...,n

 

ii/ Mỗi phần tử của X có mặt đúng m lần trong (A_i)_{i=1}^n

 

Thế thì hệ trên có một SDR

 

Chứng minh

 

. Có tổng cộng phần tử trong . Mỗi phần tử thuộc X xuất hiện đúng m lần trong (A_1,...,A_n) suy ra mỗi phần tử trong S\subset X xuất hiện không quá $latex  m$ lần. Vậy |S|\ge \frac{mk}{m}=k, Điều kiện Hall được thỏa mãn nên hệ có SDR. 

 

Định lý 3.  Xét hệ (A_i)_{i=1}^n thỏa mãn Điều kiện Hall. Với m=min\{|A_1|,|A_2|,...,|A_n|\} thế thì số SDR tối thiểu của hệ này là [m]_{min\{m,n\}}. (Ở đây ta sử dụng kí hiệu chỉnh hợp [n]_k=n(n-1)...(n-k+1))

 

Chứng minh

 

Nếu n=1, đây là điều hiển nhiên. Giả sử định lý đúng với các giá trị bé hơn n

 

Ta xét hai trường hợp như đã đặt ra trong phép chứng minh đầu tiên của định lý Hall:

 

1. Khi đó m\le |J| \le n nên hệ (A_j)_{j\in J} có tối thiểu m! SDR theo giả thiết quy nạp. Mỗi SDR của  có thể mở rộng thành 1 SDR của (A_i)_{i=1}^n, (điều này suy ra từ cách xây dựng quy nạp trong trường hợp đầu của phép chứng minh đầu tiên của định lý Hall)

 

2. Có tối thiểu m cách chọn $latex x_n$. Mỗi tập hợp trong hệ (A'_i)_{i=1}^{n-1} có tối thiểu  phần tử và thỏa mãn Điều kiện Hall nên theo giả thiết quy nạp có tối thiểu [m-1]_{min\{m-1,n-1\}} SDR cho này.

 

Vậy theo nguyên lý quy nạp, định lý được chứng minh hoàn toàn.

 

Chú ý là theo kết quả trong lời giải thứ 3 của định lý Hall thì cũng dễ dàng suy ra định lý trên.

 

B – Ứng dụng

 

1. Định lý Birkhoff – von Neumann

 

Ma trận ngẫu nhiên kép là ma trận vuông với các số hạng không âm sao cho tổng các số hạng trên mỗi hàng và tổng các số hạng trên mỗi cột đều bằng 1.

 

Ma trận thế là ma trận nhận được bằng cách hoán vị các dòng của ma trận đơn vị. Đối với ma trận cấp $n$, nếu như đánh số các dòng của ma trận đơn vị thì một ma trận thế nhận được bằng cách hoán đổi các dòng sẽ tương ứng với một phép thế cấp $n$. Do đó số các ma trận thế bằng n!

 

Định lý 4. (Birkhoff – von Neumann) Một ma trận là ngẫu nhiên kép nếu và chỉ nếu nó được biểu diễn qua một tổ hợp lồi tuyến tính các ma trận thế. Có nghĩa là X\in \Omega_n khi và chỉ khi tồn tại biểu diễn biễu diễn X=\sum_{\sigma\in S_n}{\lambda}_{\sigma}I_{\sigma}

với I_{\sigma} là ma trận thế tương ứng với phép thế \sigma\sum_{\sigma\in S_n}{\lambda}_{\sigma}=1

 

Ta sẽ chứng minh bằng quy nạp định lý này sử dụng Điều kiện Hall cho SDR hay hệ các đại diện phân biệt

 

Chứng minh

 

Đặt N là số tất cả các số hạng dương trong X , rõ ràng N\ge n. Nếu như N=n thì các số hạng này bằng 1, bản thân nó là một ma trận thế. Ta quy nạp theo giá trị của N

 

Bây giờ giả sử mệnh đúng với các giá trị bé hơn N>n, ta chứng minh mệnh đề đúng với trường hợp ma trận ngẫu nhiên kép X=(x_{ij})_nN số hạng dương. Đặt A_i=\{j \ | \ x_{ij}>0\} với i=1,2,...,n. Xét các tập A_{i_1},A_{i_2},...,A_{i_k} nào đó với , chú ý rằng k bằng tổng của tất cả các số hạng dương ở các cột i_1,i_2,...,i_k của X, và dĩ nhiên nó sẽ nhỏ hơn hoặc bằng tổng các số hạng ở những dòng mà có ít nhất một số hạng dương nằm ở các cột i_1,i_2,..,i_k, tổng này lại chính là số các dòng như vậy và bằng |A_{i_1}\cup A_{i_2}\cup....\cup A_{i_k}|.

 

Có nghĩa là điều kiện Hall đã được thỏa mãn, khi đó tồn tại một SDR, ta đặt SDR này là \sigma=\{\sigma(1),....,\sigma(n)\} đại diện cho A_1,A_2,...,A_n. Thế thì \sigma là một phép thế cấp n

 

Đặt {\lambda}_{\sigma}=min\{x_{i,\sigma(i)}, i=1,2,...,n\}.

 

Nếu {\lambda}_{\sigma}=1 thì X là ma trận thế, trường hợp ngược lại ta đặt:

 

Y=\frac{1}{1-{\lambda}_{\sigma}}(X-1-{\lambda}_{\sigma} I_{\sigma}), I_{\sigma} là ma trận thế ứng với phép thế \sigma

 

Như vậy X={\lambda}_{\sigma}I_{\lambda}+(1-{\lambda}_{\sigma})Y

 

Y là ma trận ngẫu nhiên kép với số các phần tử dương bé hơn X. Theo nguyên lý quy nạp, định lý được chứng minh hoàn toàn. \nabla

 

2. Hình vuông Latin

 

Hình vuông Latin bậc là n là bảng số vuông n\times n lập từ các số 1,2,3,...,n sao mỗi hàng và mỗi cột của nó là hoán vị của các số này. Rõ ràng là mỗi số từ tập [n]={1,2,..,n} xuất hiện đúng một lần trên mỗi hàng hoặc cột.

 

Ngoài ra còn có định nghĩa về hình chữ nhật Latin kích thước m\times n (m\le n), đó là đó là một bảng chữ nhật mà mỗi hàng của nó là một hoán vị của [n] và mỗi cột của nó là một chỉnh hợp chập m của [n].

 

Tập các số hạng của bảng vuông có thể là một tập n phần tử khác nhau, ta chọn tập [n] mà không mất tính tổng quát và đơn giản hóa sự biểu diễn.

 

Với n bất kì bạn có thể chỉ ra một hình vuông Latin bậc n như sau:

 

\begin{array}{cccccc}1 & 2 & 3 &...& k-1 & k\\2 & 3 & 4 &...& k & 1\\3 & 4 & 5 &...& 1 & 2\\...&...&...&...&...&...\\k-1 & k & 1 &...& k-3& k-2\\k & 1 & 2 &...& k-2 & k-1\end{array}

 

Bài toán đặt ra là ước lượng số hình vuông Latin cấp n, kí hiệu là L(n). Ta quan tâm đến cận trên và cận dưới của L(n)

 

Định lý 5. 

 

Chứng minh.

 

Ta có nhận xét sau: Từ một hình chữ nhật Latin kích thước m\times n (m<n) có ít nhất (n-m)! cách thêm vào một hàng để trở thành một hình chữ nhật Latin (m+1)\times n.

 

Thật vậy, gọi A_i là tập các số của [n] không có mặt ở hàng thứ i của hình chữ nhật Latin.

 

Rõ ràng các số  được thêm vào như hàng thứ k+1 để bảng số mới là hình chữ nhật Latin, khi và chỉ khi nó là một SDR của (A_1, A_2,..,A_n).

 

Ta có |A_i|=n-m, theo Hệ quả định lý Hall thì có ít nhất (n-m)! SDR. Kết quả định lý thu được là do quy nạp theo nhận xét trên. \nabla

 

Ta sẽ tiếp tục về câu chuyện cận dưới của L(n)

 

Như phần đâu đã nhấn mạnh số SDR của một hệ tập con bằng permanent ma trận nhị phân liên thuộc của hệ đó. Tuy công thức permanent có vẻ tương tự như định thức, nhưng thật sự là không có nhiều quy tắc tính toán tường minh cho permanent.

 

Ta sử dụng kết quả sau đây về cận dưới của ma trận ngẫu nhiên kép được Van der Waerden đưa ra năm 1926 và một thời coi như một giả thuyết cho đến khi có những chứng minh độc lập của Egorychev, Falikman năm 1981.

 

Định lý 6. (Van der Waerden) Nếu ma trận A ngẫu nhiên kép, thế thì \displaystyle perA\ge \frac{n!}{n^n}, đẳng thức xảy ra khi và chỉ khi mỗi số hạng của A đều bằng \displaystyle\frac{1}{n}

 

Ta có một kết quả chặt hơn hệ quả của định lý Hall đã nêu:

 

Định lý 7.  Nếu A_1,A_2,...,A_n là tập con của \{1,2,...,n\} và thỏa mãn:

 

i.  |A_i|=m

 

ii. Mỗi phần tử của [n] chứa trong đúng m tập hợp của A_1,A_2,...,A_n

 

Khi đó số SDR của hệ A_1,A_2,...,A_n tối thiểu là \displaystyle\frac{n!m^n}{n^n}

 

Chứng minh

 

Chú ý là ma trận liên thuộc A của họ A_1,A_2,...,A_n có tổng các hàng và tổng các cột bằng m.

 

Theo định lý Van der Waerden ta có \displaystyle\frac{1}{m^n}perA=per(\frac{1}{m}A)\ge \frac{n!}{n^n}

 

Từ đó \displaystyle perA\ge\frac{n!m^n}{n^n}

 

Đây cũng là điều phải chứng minh. \nabla

 

Cũng tương tự như cách chứng minh định lý 1, từ kết quả định lý 6 ta thu được ước lượng chặt hơn cho biên dưới của L(n)

L(n)\ge \frac{n!n^n}{n^n}\frac{n!(n-1)^n}{n^n}...\frac{n!2^n}{n^n}\frac{n!1^n}{n^n}=\frac{(n!)^{2n}}{n^{n^2}}

 

 

C – Một vài bài toán luyện tập

 

1. Giả sử (A_1,A_2,...,A_n) là một hệ các tập con của tập hữu hạn X. Giả sử rằng ma trận nhị phân liên thuộc của hệ này khả nghịch. Chứng tỏ rằng hệ này có một SDR.

 

2. Nếu (A_1,A_2,...,A_n) là một hệ các tập con của tập X hữu hạn thỏa mãn |\displaystyle\bigcup_{j\in J}A_j|\ge |J|-r

 

với mọi J\subset\{1,2,...,n\}, chứng minh rằng có một hệ con kích thước n-r mà có một SDR.

 

3. Cho (A_1,A_2,...,A_n), (B_1,B_2,...,B_n) là hai phân hoạch (có thứ tự) của một tập X hữu hạn.

 

M=(m_{ij})_n gọi là ma trận liên thuộc với các số hạng m_{ij}=|A_i\cap B_j|, \ i,j\in\{1,2,...,n\}.

 

Chứng minh rằng $latex M$ là ma trận ngẫu nhiên kép nếu và chỉ nếu |A_i|=|B_i|=\displaystyle\frac{|X|}{n}, \ i=1,2,...,n

 

4. Chứng minh rằng  L(n)\le\frac{ (n!)^n}{e^{n-1}}

 

 

Tài liệu tham khảo

 

 

1. Peter J. Cameron; Combinatorics – Topics, Techniques and Algorithms – Cambridge University Press, 1997.

 

2. Charles F. Laywine, Gary L. Mullen; Discrete mathematics using Latin squares – Wiley Interscience Publication, 1998.

 

3. K. A. Ribnikova; Combinatorial Analysis, Problems and Exercises (in Russian) – Nauka Publication, 1982.

 

4. H. Minc; Permanents (in Russian) – Mir Publication, 1982.

 

5. Zhi-Wei Sun; Hall’s Theorem revisited – Proc. Amer. Math. Soc. 129 (2001), no. 10, 3129–3131.

 

6. Hui-Qin Cao and Zhi-Wei Sun; On sums of distinct representatives – Acta Arith. 87 (1998), 159–169.

 

Categories: Combinatorics Tags: ,
  1. April 23, 2010 at 1:50 am

    Thank you for this useful information

  2. hungvuong
    May 2, 2010 at 3:51 am

    Cám ơn bạn đã cho một định lý rất thiết thực!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: