Đị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 lý thuyết 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

$\text{per}A=\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 $\text{per}A$ 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:

$|A_I|\ge |I|$ với mọi $I\subset E=\{1,2,\dots, n\}$

+ 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 $J$ 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 $(A_j)_{j\in J}$ nên theo giả thiết quy nạp, hệ này có SDR là $(x_j)_{j\in J}$

Với tập $K\subset E\setminus J$ , 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|$ và $|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à $(x_j)_{j\in E\setminus J}$ .
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 $J\subset \{1,2,...,n-1\}$ 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 $(B_1,...,B_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 $|B_i|=1, \ i=1,n$ . 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ố $P,Q$ 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|$ và $|Y|\le |Q|$

Mặc khác

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

và

$\bigcup_{i\in P\cap Q}B_i\subset X\cap Y$

Từ Điều kiện Hall suy ra

$|X\cup Y|\ge 1+|P\cup Q|$ và $|X\cap Y|\ge |P\cap Q|$

Á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ó $i, j$ 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 $G(V,E)$ với các đỉnh đánh số là $1,2,...,n$ sao cho $(i,j)\in E$ (đỉnh $i$ kề với $j$ ) nếu và chỉ nếu $i<n$ và $a_i\in A_j$ . Đặt

$J=\{j\in\{1,2,...,n\} \ | \$ tồn tại một đường đi từ j đến n $\}$ và $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$ và $|B|=|A|-|J|+1$

Xét $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 $a'_i$ đại diện cho $A_i, \ i\notin J$ . Rõ ràng thì $a\in B$ vì $a$ đại diện cho $A_j$ nào đó với $j\in J$

Mặt khác:

– Nếu $a\in B$ thì tồn tại $j\in J$ sao cho $a\in A_j$ . Nếu $j=n$ thì đặt $a'_n=a$ và $a'_i=a_i, \ i=1,...,n-1$ tạo thành $SDR$ thỏa mãn yêu cầu.

– Nếu $j\neq n$ thì tồn tại một đường đi từ đỉnh j đến n, đặt đường đi đó là $j_0,j_1,...,j_k$ , với $j_0=j$ và $j_k=n$ . Chú ý là $I=\{j_0,j_1,...,j_k\}\subset J$ . Ta đặt $a'_{j_0}=a, a'_{j_i}=a_{j_{i-1}}, \ j=1,...,k$ , hiển nhiên $a'_i\in A_i$ với mọi $i\in I$ . Nếu $i\notin I$ ta đặt $a'_i=a_i$ , khi đó $(a'_i)^{n}_{i=1}$ 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ệ $(A_i)_{i=1}^{n-1}$ thì có tối thiểu $1+d(n)$ cách để mở rộng thành một SDR của hệ $(A_i)_{i=1}^{n}$ . Ở đây:

$d(n)=min_{n\in I\subset\{1,...,n\}}(|\bigcup_{i\in I}A_i|-|I|)$

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ệ $(A_i)_{i=1}^n$ các tập con của tập $X$ . 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

$S= A_{i_1}\cup A_{i_2}\cup...\cup A_{i_k}, \ 1\le i_1<...< i_k\le n$ . Có tổng cộng $km$ phần tử trong $( A_{i}, A_{i_2},...,A_{i_k})$ . 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á $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 $(A_i)_{i=1}^m$ 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 $x_n$ . Mỗi tập hợp trong hệ $(A'_i)_{i=1}^{n-1}$ có tối thiểu $m-1$ 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$ và $\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})_n$ có $N$ 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 $1\le i_1< n$ , 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. $L(n)\ge n!(n-1)!...2!1!$

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ố $(x_1,x_2,...,x_n)$ đượ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 \text{per}A\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}\text{per}A=\text{per}(\frac{1}{m}A)\ge \frac{n!}{n^n}$

Từ đó $\displaystyle \text{per}A\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 $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.

	Anonymous on Tổng quan về Maplets Pack…
	Tuan Minh on GIÃ TỪ MÙA HẠ
	Spencer on Chéo hóa ma trận bằng phương p…
	định vị xe vận tải on Lý thuyết phục vụ đám đông…
	su-tu on Từ công thức Picard đến công t…

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Định lý Hall và SDRs

Published by Tuan Minh

2 thoughts on “Định lý Hall và SDRs”

Leave a comment Cancel reply

Share this:

Related

Published by Tuan Minh

2 thoughts on “Định lý Hall và SDRs”

Leave a comment Cancel reply