Luận văn Thạc sĩ Toán học: Một số bài toán phân hoạch xích đối xứng trên các Poset có hạng, hữu hạn

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

67
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Toán học: Một số bài toán phân hoạch xích đối xứng trên các Poset có hạng, hữu hạn trình bày về đưa ra hai phương pháp phân hoạch xích đối xứng (phương pháp quy nạp và phương pháp trực tiếp) cho hai Poset có hạng và hữu hạn. Mời các bạn tham khảo luận văn đề nắm bắt nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số bài toán phân hoạch xích đối xứng trên các Poset có hạng, hữu hạn

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Thân Thị Phương Trang MỘT SỐ BÀI TOÁN PHÂN HOẠCH XÍCH ĐỐI XỨNG TRÊN CÁC POSET CÓ HẠNG, HỮU HẠN LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh - 2010
PHẦN MỞ ĐẦU Kể từ khi Sperner đưa ra định lý Sperner (1928) về số cực đại các phần tử của một phản xích trên poset các tập con của tập n-phần tử thì định lý này đã được các nhà toán học khác chứng minh lại, tổng quát hóa và mở rộng đến lý thuyết về các poset. Trong đó có một cấu trúc rất đẹp là cấu trúc xích đối xứng, đặc biệt là sự phân hoạch xích đối xứng trên các poset và các ứng dụng của nó. Vì trong các dạng poset, ta thường quan tâm đến các poset có hạng và hữu hạn nên ở luận văn này ta chỉ chú ý đến các poset dạng đó, đặc biệt là poset P(S) các tập con của tập n-phần tử S, poset P(m) các ước nguyên dương của số nguyên m cho trước và poset tích trực tiếp của chúng. Năm 1951, nhà toán học de Bruijn đã chứng minh poset P(m) các ước nguyên dương của số nguyên m cho trước có một phân hoạch thành các xích đối xứng – tức P(m) có thể biểu diễn như hợp rời rạc các xích đối xứng. Kết quả này được xây dựng nhờ vào phương pháp quy nạp theo số các ước nguyên tố phân biệt của số m. Nhưng khi m có khá nhiều các ước nguyên tố thì phương pháp này trở nên phức tạp. Vì vậy vào năm 1976, trong xu thế tìm kiếm các phương pháp phân hoạch trực tiếp cho poset P(m), hai nhà toán học Greene và Kleitman đã đạt được một kết quả khá đẹp ; họ đưa ra được một phân hoạch trực tiếp xích đối xứng cho poset P(S) các tập con của tập n – phần tử S. Kết quả này là lời giải cho một trường hợp đặc biệt ( k1  k2  ...  kn  1 ) của bài toán phân hoạch trực tiếp xích đối xứng poset P(m) với m  p1k1 . p2k2 ... pnkn , nhưng đồng thời cũng là cơ sở để ta giải quyết bài toán này trong trường hợp tổng quát. Trong luận văn này, tôi sẽ trình bày cả hai phương pháp (quy nạp và trực tiếp) để phân hoạch hai poset (P(S) và P(m)) thành các xích đối xứng và chỉ ra rằng cả hai phương pháp này đều như nhau. Sau đó, tôi sẽ đi sâu vào cấu trúc của một phân hoạch xích đối xứng xét về khía cạnh số lượng xích đối xứng, size của các xích đối xứng và số các xích đối xứng có cùng size i. Cuối cùng, tôi đưa ra một số ứng dụng của phương pháp phân hoạch trực tiếp xích đối xứng để tính số phản xích của poset P(S).
CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ 1.1.Quan hệ thứ tự: Định nghĩa 1.1.1: “  ” được gọi là quan hệ thứ tự trên tập hợp P nếu x, y, z  P ta có: i) x  x ii) x  y, y  x  x  y iii) x  y, y  z  x  z Ví dụ 1.1.1: Các quan hệ sau là quan hệ thứ tự:  Quan hệ bao hàm trên tập các tập con của một tập hợp S.  Quan hệ chia hết trên tập các ước nguyên dương của một số nguyên m. 1.2. Tập sắp thứ tự bộ phận (poset): Định nghĩa 1.2.1: Tập hợp P với quan hệ thứ tự  được gọi là một tập sắp thứ tự bộ phận, hay còn gọi là một poset. Ví dụ 1.2.1: Các tập hợp sau là các poset:  Tập các tập con của một tập hợp S với quan hệ bao hàm.  Tập các ước nguyên dương của một số nguyên m với quan hệ chia hết. 1.3. Một số khái niệm cơ bản trên một poset: Trong một poset ( P,  ) ta có các khái niệm cơ bản sau:  Hai phần tử x, y  P được gọi là so sánh được với nhau nếu x  y hoặc y  x .  Nếu x  y và x  y thì ta viết x  y .  Nếu x  y và không có z  P : x  z  y thì ta nói y phủ x .  Nếu có duy nhất z  P : z  x, x  P thì ta gọi z là phần tử bé nhất của P, ký hiệu là 0. Ví dụ 1.3.1: +) Phần tử 0 của poset các tập con của tập n phần tử S là tập  . +) Phần tử 0 của poset các ước nguyên dương của một số nguyên m là 1.  x  P được gọi là phần tử tối tiểu của P nếu không có y  P : y  x .  x  P được gọi là phần tử tối đại của P nếu không có y  P : x  y .  Nếu x1  x2  ...  xn thì ta nói x1 , x2 ,..., xn tạo thành một xích.  Xích x1  x2  ...  xn thỏa xi 1 phủ xi , i  n được gọi là một xích bão hòa. 1.4. Hàm hạng, poset có hạng:
Giả sử ( P,  ) là poset có tính chất (*): x, y  P, x  y thì tất cả những xích bão hòa từ x đến y đều có cùng lực lượng. Đặc biệt, x  P thì tất cả những xích bão hòa từ 0 đến x cũng sẽ có cùng lực lượng. Khi đó nếu ta định nghĩa độ dài của một xích là lực lượng của xích đó trừ đi 1 thì ta có thể định nghĩa hạng r ( x) của một phần tử x là độ dài của một xích bão hòa từ 0 đến x . Định nghĩa 1.4.1: Cho ( P,  ) là poset có tính chất (*) như trên. Khi đó hàm số r : P  R  x  r ( x) được gọi là hàm hạng của P, trong đó r ( x) là hạng của phần tử x . Một poset có tính chất (*) như trên được gọi là poset có hạng, với hàm hạng r. Để dễ dàng trong việc sử dụng hàm hạng của một poset, ta tìm các tương đương của nó như sau: Mệnh đề 1.4.1: Cho poset ( P,  ) với hàm hạng r. Khi đó ta có: (i) r ( x)  , x  P và r (0)  0 ; trong đó là tập số tự nhiên. (ii) Nếu x, y  P , x phủ y thì r ( x)  r ( y )  1 . Chứng minh (i) x  P thì lực lượng C của tất cả các xích bão hòa từ 0 đến x thỏa C  1, C  . Suy ra độ dài của tất cả các xích bão hòa từ 0 đến x là r ( x)  C  1  0, r ( x)  . Đặc biệt r (0)  0 . (ii) Giả sử một xích bão hòa từ 0 đến y là : 0  y1  y2  ...  yk  y  0  y1  y2  ...  yk  y  x là một xích bão hòa từ 0 đến x. r ( y )  k  2  1  k  1 Ta có:   r ( x)  r ( y )  1 .  r ( x)  k  3  1  k  2 Ví dụ 1.4.1 :  Poset P(S) các tập con của tập n-phần tử S là một poset có hạng, với hàm hạng r ( A)  A , A  P ( S ) .  Poset P(m) các ước nguyên dương của một số nguyên m là một poset có hạng, với hàm hạng r (d )  số các thừa số nguyên tố trong phân tích của d , d  P(m) . Ví dụ: Với m  100  22.52 , d  22.5 m  r (d )  3 1.5. Xích đối xứng: Định nghĩa 1.5.1: Cho poset P với hàm hạng r . Khi đó ta nói các phần tử x1 , x2 ,..., xh tạo thành một xích đối xứng nếu: i) xi 1 phủ xi , i  h
ii) r ( x1 )  r ( xh )  r ( P ) , với r ( P) là hạng lớn nhất trong P. Ví dụ 1.5.1:  Trong poset P(S) các tập con của tập n-phần tử S, A1 , A2 ,..., Ah  P( S ) lập thành một xích đối xứng nếu: i) Ai  Ai 1 và Ai 1  Ai  1, i  h . ii) A1  Ah  r ( P( S ))  n .  Trong poset P(m) các ước nguyên dương của một số nguyên m, d1 , d 2 ,..., d h  P lập thành một xích đối xứng nếu: di 1 i) di di 1 và là một số nguyên tố, i  h . di ii) r (d1 )  r (d h )  r ( P(m))  r (m) .
CHƯƠNG 2: MỘT SỐ BÀI TOÁN PHÂN HOẠCH XÍCH ĐỐI XỨNG TRÊN CÁC POSET CÓ HẠNG, HỮU HẠN Trong chương này, tôi sẽ trình bày cả hai phương pháp (quy nạp và trực tiếp) để phân hoạch hai poset (P(S) và P(m)) thành các xích đối xứng, chỉ ra rằng cả hai phương pháp này đều như nhau và đưa ra một số ví dụ minh họa. Sau đó, tôi sẽ đi sâu vào cấu trúc của một phân hoạch xích đối xứng xét về khía cạnh số lượng xích đối xứng, size của các xích đối xứng và số các xích đối xứng có cùng size i. Cuối cùng, tôi đưa ra một số ứng dụng của phương pháp phân hoạch trực tiếp xích đối xứng để tính số phản xích của poset P(S). Do tập n-phần tử S hữu hạn nên ta có thể đánh số thứ tự các phần tử của S từ 1 đến n. Vì vậy trong toàn bộ chương này ta có thể quy ước chọn tập n-phần tử S là tập n số tự nhiên khác 0 đầu tiên, tức S  1, 2,..., n . 2.1. MỘT SỐ ĐỊNH NGHĨA: Định nghĩa 2.1.1: Một poset P có hạng, hữu hạn được gọi là được phân hoạch thành các xích đối xứng nếu nó được biểu diễn như hợp rời rạc của một số nào đó các xích đối xứng (nghĩa là các xích đối xứng này có giao nhau bằng rỗng và hợp của chúng chính bằng poset P) Định nghĩa 2.1.2: Một tập A các tập con  As s  1,k của tập n-phần tử S được gọi là một phản xích nếu Ai  A j , i  j; i, j 1, k . Định nghĩa 2.1.3: Một xích đối xứng trong poset P được gọi là có size k nếu nó có lực lượng bằng k. 2.2. PHÂN HOẠCH XÍCH ĐỐI XỨNG BẰNG PHƯƠNG PHÁP QUY NẠP: 2.2.1. Phân hoạch xích đối xứng cho poset P(S) các tập con của tập n-phần tử S: Định lý 2.2.1.1: Poset P(S) các tập con của tập n-phần tử S có một phân hoạch thành các xích đối xứng. Chứng minh: Ta sẽ chứng minh bằng phương pháp quy nạp theo n. * Với n = 1 thì S  1 nên P ( S )  , 1 có một xích đối xứng duy nhất:   1 , chứa tất cả các phần tử của P(S). Do đó định lý đúng với n = 1.
* Giả sử định lý đúng với n = k, nghĩa là với Sk  1, 2,..., k thì P(Sk) có một phân hoạch thành các xích đối xứng. Ta sẽ chứng minh định lý đúng với n = k + 1. Lấy Sk 1  1, 2,..., k , k  1 , ta sẽ xây dựng một phân hoạch xích đối xứng cho P(Sk+1) từ phân hoạch xích đối xứng của P(Sk) theo giả thiết quy nạp. Lấy A1  A2  ...  Am là một xích đối xứng bất kỳ trong phân hoạch xích đối xứng của P(Sk). Ta xét hình chữ nhật sau: A1  A2  ...  Am1  Am A1  k  1  A2  k  1  ...  Am1  k  1  Am  k  1 “Bóc” lớp ngoài cùng của hình chữ nhật trên ta được xích: A1  A2  ...  Am  Am  k  1 (2.1) Ta có : +) Ai  Ai 1 , Ai 1  Ai  1, i  m và Am  Am  k  1 , Am  k  1  Am  1 +) A1  Am  k  1  A1  Am  1  k  1 Do đó xích (2.1) là một xích đối xứng trong P(Sk+1). Tương tự lớp còn lại của hình chữ nhật trên cho ta xích : A1  k  1  A2  k  1  ...  Am1  k  1 (2.2) Ta có : +) Ai  k  1  Ai 1  k  1 , i  m  1, và Ai 1  k  1  Ai 1  1  Ai  1  1  Ai  k  1  1 +) A1  k  1  Am1  k  1  A1  1  Am1  1  A1  Am  1  k  1 Nên (2.2) cũng là một xích đối xứng trong P(Sk+1). Mặt khác: P( Sk 1 )  P( Sk )   Ai  k  1 Ai  P( Sk ) nên khi tiếp tục quá trình trên đối với tất cả các xích đối xứng của P(Sk), ta sẽ tìm được các xích đối xứng của P(Sk+1) mà chúng chứa tất cả các phần tử của P(Sk+1). Như vậy ta đã xây dựng được một phân hoạch xích đối xứng của poset P(Sk+1).  Ví dụ 2.2.1.1: Xây dựng một phân hoạch xích đối xứng của poset P(S6), với S6  1, 2,3, 4,5, 6 Giải Để xây dựng được một phân hoạch xích đối xứng của P(S6), ta phải xây dựng lần lượt các phân hoạch xích đối xứng của P(S1), P(S2), P(S3), P(S4) và P(S5).
 Đối với P(S1): Ta có: P ( S1 )  , 1 có một xích đối xứng duy nhất là   1 nên P(S1) có một phân hoạch xích đối xứng là:   1 .  Đối với P(S2): Ta xét hình chữ nhật sau:   1 2  1, 2 “Bóc” các lớp của hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(S2) như sau: 2   1  1, 2  Đối với P(S3): Ta xét 2 hình chữ nhật sau: 2 2,3   1  1, 2 3  1,3  1, 2,3 “Bóc” các lớp của 2 hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(S3) như sau: 2  2,3 3  1,3   1  1, 2  1, 2,3  Đối với P(S4): Ta xét 3 hình chữ nhật sau: 2  2,3 2, 4  2,3, 4 3  1,3 3, 4  1,3, 4   1  1, 2  1, 2,3 4  1, 4  1, 2, 4  1, 2,3, 4 “Bóc” các lớp của 3 hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(S4) như sau: 2, 4 3, 4
2  2,3  2,3, 4 3  1,3  1,3, 4 4  1, 4  1, 2, 4   1  1, 2  1, 2,3  1, 2,3, 4  Đối với P(S5): Ta xét 6 hình chữ nhật sau: 2, 4 2, 4,5 3, 4 3, 4,5 2  2,3  2,3, 4 2,5  2,3,5  2,3, 4,5 3  1,3  1,3, 4 3,5  1,3,5  1,3, 4,5 4  1, 4  1, 2, 4 4,5  1, 4,5  1, 2, 4,5   1  1, 2  1, 2,3  1, 2,3, 4 5  1,5  1, 2,5  1, 2,3,5  1, 2,3, 4,5 “Bóc” các lớp của 6 hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(S5) như sau: 2, 4  2, 4,5 3, 4  3, 4,5 2,5  2,3,5 3,5  1,3,5 4,5  1, 4,5 2  2,3  2,3, 4  2,3, 4,5 3  1,3  1,3, 4  1,3, 4,5 4  1, 4  1, 2, 4  1, 2, 4,5
5  1,5  1, 2,5  1, 2,3,5   1  1, 2  1, 2,3  1, 2,3, 4  1, 2,3, 4,5  Đối với P(S6): Ta xét 10 hình chữ nhật sau: 2, 4  2, 4,5 2, 4, 6  2, 4,5, 6 3, 4  3, 4,5 3, 4, 6  3, 4,5, 6 2,5  2,3,5 2,5, 6  2,3,5, 6 3,5  1,3,5 3,5, 6  1,3,5, 6 4,5  1, 4,5 4,5, 6  1, 4,5, 6 2  2,3  2,3, 4  2,3, 4,5 2, 6  2,3, 6  2,3, 4, 6  2,3, 4,5, 6 3  1,3  1,3, 4  1,3, 4,5 3, 6  1,3, 6  1,3, 4, 6  1,3, 4,5, 6 4  1, 4  1, 2, 4  1, 2, 4,5 4, 6  1, 4, 6  1, 2, 4, 6  1, 2, 4,5, 6 5  1,5  1, 2,5  1, 2,3,5 5, 6  1,5, 6  1, 2,5, 6  1, 2,3,5, 6   1  1, 2  1, 2,3  1, 2,3, 4  1, 2,3, 4,5 6  1, 6  1, 2, 6  1, 2,3, 6  1, 2,3, 4, 6  1, 2,3, 4,5, 6 “Bóc” các lớp của 10 hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(S6) như sau: 2, 4, 6 3, 4, 6
2,5, 6 3,5, 6 4,5, 6 2, 4  2, 4,5  2, 4,5, 6 3, 4  3, 4,5  3, 4,5, 6 2,5  2,3,5  2,3,5, 6 3,5  1,3,5  1,3,5, 6 4,5  1, 4,5  1, 4,5, 6 2, 6  2,3, 6  2,3, 4, 6 3, 6  1,3, 6  1,3, 4, 6 4, 6  1, 4, 6  1, 2, 4, 6 5, 6  1,5, 6  1, 2,5, 6 2  2,3  2,3, 4  2,3, 4,5  2,3, 4,5, 6 3  1,3  1,3, 4  1,3, 4,5  1,3, 4,5, 6 4  1, 4  1, 2, 4  1, 2, 4,5  1, 2, 4,5, 6 5  1,5  1, 2,5  1, 2,3,5  1, 2,3,5, 6 6  1, 6  1, 2, 6  1, 2,3, 6  1, 2,3, 4, 6   1  1, 2  1, 2,3  1, 2,3, 4  1, 2,3, 4,5  1, 2,3, 4,5, 6 2.2.2. Phân hoạch xích đối xứng cho poset P(m) các ước nguyên dương của số nguyên m cho trước: Định lý 2.2.2.1: Poset P(m) các ước nguyên dương của số nguyên m cho trước có một phân hoạch thành các xích đối xứng. Chứng minh: Gọi n là số các ước nguyên tố phân biệt của m. Ta sẽ chứng minh bằng phương pháp quy nạp theo n.  * Với n = 1 thì m có dạng m  p . Khi đó P (m)  1, p, p 2 ,..., p  có một xích đối xứng duy nhất: 1  p  p 2  ...  p , chứa tất cả các phần tử của P(m). Do đó định lý đúng với n = 1.
* Giả sử định lý đúng với n = k, nghĩa là nếu m có k ước nguyên tố phân biệt thì P(m) có một phân hoạch thành các xích đối xứng. * Ta sẽ chứng minh định lý đúng với n = k +1. Xét số nguyên m có (k +1) ước nguyên tố phân biệt, tức m  m1 p , trong đó m1 có k ước nguyên tố phân biệt và số nguyên tố p không là ước của m1. Ta sẽ chỉ ra cách xây dựng các xích đối xứng của P(m) từ các xích đối xứng của P(m1). Lấy d1  d 2  ...  d h là một xích đối xứng bất kỳ trong phân hoạch xích đối xứng của P(m1) theo giả thiết quy nạp. Xét tất cả các ước của m có dạng di p  , 1  i  h, 0     và sắp xếp tất cả các ước này theo hình chữ nhật sau: d1  d2  ...  d h 2  d h1  dh d1 p  d2 p  ...  d h2 p  d h1 p  dh p d1 p 2  d2 p 2  ...  d h2 p 2  d h1 p 2  dh p2      d1 p 1  d 2 p 1  ...  d h2 p 1  d h 1 p 1  d h p 1 d1 p  d 2 p  ...  d h 2 p  d h1 p  d h p Ta “bóc” các xích đã được chỉ ra trên hình chữ nhật trên.  Lớp ngoài cùng của hình chữ nhật trên cho ta xích đầu tiên: d1  d 2  ...  d h2  d h1  d h  d h p  d h p 2  ...  d h p (2.3) di 1 Ta có: +) di di 1 , là một số nguyên tố, i  h . di d h p i 1 +) d h pi d h pi 1 ,  p cũng là số nguyên tố, i   . d h pi +) r (d1 )  r (d h p )  r (d1 )  r (d h )  r ( p )  r (m1 )  r ( p )  r (m) . Vậy (2.3) là một xích đối xứng của P(m).  Tương tự, lớp thứ hai của hình chữ nhật trên cho ta xích : d1 p  d 2 p  ...  d h2 p  d h1 p  d h1 p 2  ...  d h1 p (2.4) cũng là một xích đối xứng của P(m).  Cứ tiếp tục như vậy, 2 lớp cuối cùng của hình chữ nhật trên cho ta 2 xích : d1 p 1  d 2 p 1  d 2 p và d1 p ,cũng là các xích đối xứng của P(m).
   Do m  m1 p (p không là ước của m1) nên P (m)  P(m1 )  dp j d  P(m1 ), 1  j   . Do đó, cứ tiếp tục quá trình trên đối với tất cả các xích đối xứng trong phân hoạch xích đối xứng của P(m1) thì ta được các xích đối xứng rời nhau của P(m), mà chúng chứa tất cả các phần tử của P(m). Như vậy, ta đã xây dựng được một phân hoạch xích đối xứng cho poset P(m).  Ví dụ 2.2.2.1: Xây dựng một phân hoạch xích đối xứng cho P (68600)  P(23.52.73 ) . Giải Để xây dựng một phân hoạch xích đối xứng cho P(23.52.73 ) , ta phải lần lượt xây dựng các phân hoạch xích đối xứng cho P (23 ) và P (23.52 )    Đối với P(23 ) : Ta có : P (23 )  1, 2, 22 , 23 nên ta được một phân hoạch xích đối xứng của P (23 ) là : 1  2  22  23 .  Đối với P (23.52 ) : Ta xét hình chữ nhật sau : 1  2  22  23 1.5  2.5  22.5  23.5 1.52  2.52  22.52  23.52 Sau khi “bóc” các lớp của hình chữ nhật trên ta được một phân hoạch xích đối xứng của P (23.52 ) là : 1.52  2.52 1.5  2.5  22.5  22.52 1  2  22  23  23.5  23.52  Đối với P(23.52.73 ) : Ta xét 3 hình chữ nhật sau : 1.52  2.52 1.52.7  2.52.7 1.52.7 2  2.52.7 2 1.52.73  2.52.73 1.5  2.5  22.5  22.52 1.5.7  2.5.7  22.5.7  22.52.7 1.5.7 2  2.5.7 2  22.5.7 2  22.52.7 2 1.5.73  2.5.73  22.5.73  22.52.73
1  2  22  23  23.5  23.52 1.7  2.7  22.7  23.7  23.5.7  23.52.7 1.7 2  2.7 2  22.7 2  23.7 2  23.5.7 2  23.52.7 2 1.73  2.73  22.73  23.73  23.5.73  23.52.73 Sau khi “bóc” các lớp của 3 hình chữ nhật trên ta được một phân hoạch xích đối xứng của P(23.52.73 ) như sau : 1.5.73 1.52.7  1.52.7 2  1.52.73 1.5.7 2  2.5.7 2  2.5.73 1.73  2.73  22.73 1.52  2.52  2.52.7  2.52.7 2  2.52.73 1.5.7  2.5.7  22.5.7  22.5.7 2  22.5.73 1.7 2  2.7 2  22.7 2  23.7 2  23.73 1.5  2.5  22.5  22.52  22.52.7  22.52.7 2  22.52.73 1.7  2.7  22.7  23.7  23.5.7  23.5.7 2  23.5.73 1  2  22  23  23.5  23.52  23.52.7  23.52.7 2  23.52.73 2.2.3. Phân hoạch xích đối xứng cho tích trực tiếp các poset: Định nghĩa 2.2.3.1 : Nếu P, Q là những poset có hạng, với hàm hạng tương ứng là r , r ' thì tích trực tiếp của P và Q, ký hiệu  p1  p2 trong P là P  Q  ( p, q) p  P, q  Q , là một poset với quan hệ thứ tự : ( p1 , q1 )  ( p2 , q2 )   . q1  q2 trong Q Poset tích trực tiếp P  Q có hàm hạng  được định nghĩa bởi  ( p, q)  r ( p)  r '(q), ( p, q)  P  Q Ví dụ 2.2.3.1 : Cho P(S) là poset tất cả các tập con của tập S  1, 2,3 và P (52 ) là poset tất cả các ước nguyên dương của số nguyên 52 .   Hay P ( S )  ; 1 ; 2 ; 3 ;1, 2 ; 1,3 ; 2,3 ;1, 2,3 và P(52 )  1,5,52 . Khi đó poset tích trực tiếp của P(S) và P(52 ) là : P ( S )  P(52 )  {(,1);(,5);(,52 );({1},1);({1},5);({1},52 );({2},1);({2},5);({2},52 ); ({3},1);({3},5);({3},52 );({1, 2},1);({1, 2},5);({1, 2},52 );({1,3},1);({1,3},5);({1,3},52 );
({2,3},1);({2,3},5);({2,3},52 );({1, 2,3},1);({1, 2,3},5);({1, 2,3},52 )} Trong đó :  ({2,3},5)  r ({2,3})  r '(5)  2  1  3  (1 ,1)  r ({1})  r '(1)  1  0  1 (với r , r ',  lần lượt là hàm hạng của các poset P(S), P (52 ) và P ( S )  P (52 ) ) Ví dụ 2.2.3.2 : Cho P(33 ) là poset tất cả các ước nguyên dương của số nguyên m1  33 và P(7 2 ) là poset tất cả các ước nguyên dương của số nguyên m2  7 2 .   Hay P (33 )  1,3,32 ,33 và P (7 2 )  1, 7, 7 2 .  Khi đó poset tích trực tiếp của P(33 ) và P (7 2 ) là : P (33 )  P(7 2 )  {(1,1);(1, 7);(1, 7 2 ); (3,1);(3, 7);(3, 7 2 );(32 ,1);(32 , 7);(32 , 7 2 );(33 ,1);(33 , 7);(33 , 7 2 )} Trong đó :  (32 , 7)  r (32 )  r '(7)  2  1  3  (1, 7 2 )  r (1)  r '(7 2 )  0  2  2 ( r , r ',  lần lượt là hàm hạng của các poset P(33 ) , P (7 2 ) và P (33 )  P(7 2 ) ). Trong ví dụ 2.2.3.2 nếu ta đồng nhất ( p, q) với p.q thì dễ thấy poset tích trực tiếp P (33 )  P(7 2 ) chính là poset P (33.7 2 ) . Từ điều này ta có mệnh đề sau : Mệnh đề 2.2.3.1 : Cho p, q là hai số nguyên tố phân biệt. Với k, h là hai số nguyên dương bất kỳ thì poset tích trực tiếp P ( p k )  P (q h ) chính là poset P( p k .q h ) . Từ mệnh đề 2.2.3.1 ta có thể mở rộng ra mệnh đề sau đây : Mệnh đề 2.2.3.2 : Cho p1 , p2 ,..., pn là n số nguyên tố phân biệt. Với k1, k2 ,..., kn là n số nguyên dương bất kỳ thì poset tích trực tiếp P ( p1k1 )  P ( p2k2 )  ...  P( pnkn ) chính là poset P ( p1k1 . p2k2 ... pnkn ) . (Ở đây, poset tích trực tiếp của n poset được mở rộng từ định nghĩa 2.2.3.1 như sau: Nếu P1 , P2 ,..., Pn là các poset có hàm hạng tương ứng là r1 , r2 ,..., rn thì poset tích trực tiếp của P1 , P2 ,..., Pn , ký hiệu là P1  P2  ...  Pn  ( p1 , p2 ,..., pn ) pi  Pi , i  1,..., n , là một poset với quan hệ thứ tự như sau : ( p1 , p2 ,..., pn )  ( p '1 , p '2 ,..., p 'n )  pi  p 'i trong Pi , i  1, 2,..., n ). Poset P1  P2  ...  Pn có hàm hạng  được định nghĩa là : p( p1 , p2 ,..., pn )  r1 ( p1 )  r2 ( p2 )  ...  rn ( pn ), ( p1 , p2 ,..., pn )  P1  P2  ...  Pn ) Theo mệnh đề 2.2.3.1 và định lý 2.2.2.1 : Nếu p,q là hai số nguyên tố phân biệt và k, h là hai số nguyên dương bất kỳ thì các poset P ( p k ), P(q h ) có phân hoạch xích đối xứng và ta dễ dàng có được
phân hoạch xích đối xứng của poset P ( p k )  P (q h ) từ phân hoạch xích đối xứng của poset P( p k .q h ) . Vấn đề bây giờ là : Liệu với P,Q là hai poset tùy ý có phân hoạch xích đối xứng thì poset tích trực tiếp P  Q có pơhân hoạch xích đối xứng không ? Và nếu có thì chúng được xây dựng như thế nào ? Định lý 2.2.3.1 : Nếu P, Q là hai poset có hàm hạng tương ứng là r , r ' và đều có phân hoạch xích đối xứng thì poset tích trực tiếp P  Q với hàm hạng  cũng có phân hoạch xích đối xứng. Chứng minh : Giả sử P  C1  C2  ...  Cm và Q  D1  D2  ...  Dn là các phân hoạch xích đối xứng của P và Q. Ở đây Ci , i  1,..., m , là các xích đối xứng trong P và D j , j  1,..., n , là các xích đối xứng trong Q. Lấy bất kỳ hai xích đối xứng Ci , D j tương ứng trong P, Q như sau: Ci : c0  c1  ...  ck , với r (c0 )  t , r (ck )  T , t  T  r ( P) , và D j : d 0  d1  ...  d h , với r '(d0 )  s, r '(d h )  S , s  S  r '(Q) . Ta chứng minh tương tự như định lý 2.2.2.1: Xét hình chữ nhật sau: E0 : (c0 , d 0 )  (c1 , d0 )  ...  (ck 2 , d 0 )  (ck 1, d 0 )  (ck , d 0 ) E1 : (c0 , d1 )  (c1, d1 )  ...  (ck 2 , d1 )  (ck 1 , d1 )  (ck , d1 ) E2 : (c0 , d 2 )  (c1, d 2 )  ...  (ck 2 , d 2 )  (ck 1, d 2 )  (ck , d 2 )      Eh1 : (c0 , d h1 )  (c1 , d h1 )  ...  (ck 2 , d h 1 )  (ck 1 , d h 1 )  (ck , d h1 ) Eh : (c0 , d h )  (c1 , d h )  ...  (ck 2 , d h )  (ck 1, d h )  (ck , d h ) “Bóc” các lớp của hình chữ nhật trên ta được (h + 1) xích E0 , E1 , E2 ,..., Eh1 , Eh như được chỉ trong hình chữ nhật trên. Ta sẽ chứng minh (h + 1) xích này là các xích đối xứng trong poset tích trực tiếp P  Q . Xét xích E j : (c0 , d j )  (c1 , d j )  ...  (ck  j , d j )  (ck  j , d j 1 )  ...  (ck  j , d h ); j  0,1,..., h j  0,1,..., h : Ta dễ thấy các xích E j là các xích bão hòa. Mặt khác ta có:  (c0 , d j )   (ck  j , d h )  r (c0 )  r '(d j )  r (ck  j )  r '(d h )  t  ( s  j )  (t  k  j )  S  t  s  (t  k )  S  t  s  T  S  (t  T )  ( s  S )  r ( P)  r '(Q)   ( P  Q) . Vậy các E j , j  0,1,..., h , là các xích đối xứng trong poset tích trực tiếp P  Q . Bằng cách xét từng cặp xích đối xứng Ci và D j ( i  1,..., m; j  1,..., n ) như trên ta sẽ có được một phân hoạch xích đối xứng cho poset tích trực tiếp P  Q . 
Ví dụ 2.2.3.3 :Tìm một phân hoạch xích đối xứng của poset tích trực tiếp P ( S )  P(23.52 ) , trong đó P(S) là poset tất cả các tập con của tập 4 phần tử S  1, 2,3, 4 và P (23.52 ) là poset tất cả các ước nguyên dương của số nguyên m  23.52 . Giải Theo ví dụ 2.2.1.1 và ví dụ 2.2.2.1 ta có phân hoạch xích đối xứng của poset P(S) và poset P (23.52 ) như sau : Phân hoạch xích đối xứng của P(S) : P ( S )  C1  C2  C3  C4  C5  C6 C1: 2, 4 C2: 3, 4 C3: 2  2,3  2,3, 4 C4: 3  1,3  1,3, 4 C5: 4  1, 4  1, 2, 4 C6:   1  1, 2  1, 2,3  1, 2,3, 4 Phân hoạch xích đối xứng của P (23.52 ) : P (23.52 )  D1  D2  D3 D1 : 1.52  2.52 D2 : 1.5  2.5  22.5  22.52 D3: 1  2  22  23  23.5  23.52 Ta xét các hình chữ nhật hình thành từ các cặp xích đối xưng sau : * Các cặp xích dối xứng : (C1 , D1 ), (C1 , D2 ), (C1 , D3 ) ({2, 4},1.52 ) ({2, 4}, 2.52 ) ({2, 4},1.5) ({2, 4}, 2.5) ({2, 4}, 22.5) ({2, 4}, 22.52 )
({2, 4},1) ({2, 4}, 2) ({2, 4}, 22 ) ({2, 4}, 23 ) ({2, 4}, 23.5) ({2, 4}, 23.52 ) * Các cặp xích đối xứng : (C2 , D1 ), (C2 , D2 ), (C2 , D3 ) ({3, 4},1.52 ) ({3, 4}, 2.52 ) ({3, 4},1.5) ({3, 4}, 2.5) ({3, 4}, 22.5) ({3, 4}, 22.52 ) ({3, 4},1) ({3, 4}, 2) ({3, 4}, 22 ) ({3, 4}, 23 ) ({3, 4}, 23.5) ({3, 4}, 23.52 ) * Các cặp xích đối xứng : (C3 , D1 ), (C3 , D2 ), (C3 , D3 ) ({2},1.52 )  ({2,3},1.52 )  ({2,3, 4},1.52 ) ({2}, 2.52 )  ({2,3}, 2.52 )  ({2,3, 4}, 2.52 ) ({2},1.5)  ({2,3},1.5)  ({2,3, 4},1.5) ({2}, 2.5)  ({2,3}, 2.5)  ({2,3, 4}, 2.5) ({2}, 22.5)  ({2,3}, 22.5)  ({2,3, 4}, 22.5) ({2}, 22.52 )  ({2,3}, 22.52 )  ({2,3, 4}, 22.52 )
({2},1)  ({2,3},1)  ({2,3, 4},1) ({2}, 2)  ({2,3}, 2)  ({2,3, 4}, 2) ({2}, 22 )  ({2,3}, 22 )  ({2,3, 4}, 22 ) ({2}, 23 )  ({2,3}, 23 )  ({2,3, 4}, 23 ) ({2}, 23.5)  ({2,3}, 23.5)  ({2,3, 4}, 23.5) ({2}, 23.52 )  ({2,3}, 23.52 )  ({2,3, 4}, 23.52 ) * Các cặp xích đối xứng : (C4 , D1 ), (C4 , D2 ), (C4 , D3 ) ({3},1.52 )  ({1,3},1.52 )  ({1,3, 4},1.52 ) ({3}, 2.52 )  ({1,3}, 2.52 )  ({1,3, 4}, 2.52 ) ({3},1.5)  ({1,3},1.5)  ({1,3, 4},1.5) ({3}, 2.5)  ({1,3}, 2.5)  ({1,3, 4}, 2.5) ({3}, 22.5)  ({1,3}, 22.5)  ({1,3, 4}, 22.5) ({3}, 22.52 )  ({1,3}, 22.52 )  ({1,3, 4}, 22.52 ) ({3},1)  ({1,3},1)  ({1,3, 4},1) ({3}, 2)  ({1,3}, 2)  ({1,3, 4}, 2) ({3}, 22 )  ({1,3}, 22 )  ({1,3, 4}, 22 ) ({3}, 23 )  ({1,3}, 23 )  ({1,3, 4}, 23 ) ({3}, 23.5)  ({1,3}, 23.5)  ({1,3, 4}, 23.5) ({3}, 23.52 )  ({1,3}, 23.52 )  ({1,3, 4}, 23.52 ) * Các cặp xích đối xứng : (C5 , D1 ), (C5 , D2 ), (C5 , D3 ) ({4},1.52 )  ({1, 4},1.52 )  ({1, 2, 4},1.52 ) ({4}, 2.52 )  ({1, 4}, 2.52 )  ({1, 2, 4}, 2.52 ) ({4},1.5)  ({1, 4},1.5)  ({1, 2, 4},1.5) ({4}, 2.5)  ({1, 4}, 2.5)  ({1, 2, 4}, 2.5) ({4}, 22.5)  ({1, 4}, 22.5)  ({1, 2, 4}, 22.5)
({4}, 22.52 )  ({1, 4}, 22.52 )  ({1, 2, 4}, 22.52 ) ({4},1)  ({1, 4},1)  ({1, 2, 4},1) ({4}, 2)  ({1, 4}, 2)  ({1, 2, 4}, 2) ({4}, 22 )  ({1, 4}, 22 )  ({1, 2, 4}, 22 ) ({4}, 23 )  ({1, 4}, 23 )  ({1, 2, 4}, 23 ) ({4}, 23.5)  ({1, 4}, 23.5)  ({1, 2, 4}, 23.5) ({4}, 23.52 )  ({1, 4}, 23.52 )  ({1, 2, 4}, 23.52 ) * Các cặp xích đối xứng : (C6 , D1 ), (C6 , D2 ), (C6 , D3 ) (,1.52 )  ({1},1.52 )  ({1, 2},1.52 )  ({1, 2,3},1.52 )  ({1, 2,3, 4},1.52 ) (, 2.52 )  ({1}, 2.52 )  ({1, 2}, 2.52 )  ({1, 2,3}, 2.52 )  ({1, 2,3, 4}, 2.52 ) (,1.5)  ({1},1.5)  ({1, 2},1.5)  ({1, 2,3},1.5)  ({1, 2,3, 4},1.5) (, 2.5)  ({1}, 2.5)  ({1, 2}, 2.5)  ({1, 2,3}, 2.5)  ({1, 2,3, 4}, 2.5) (, 22.5)  ({1}, 22.5)  ({1, 2}, 22.5)  ({1, 2,3}, 22.5)  ({1, 2,3, 4}, 22.5) (, 22.52 )  ({1}, 22.52 )  ({1, 2}, 22.52 )  ({1, 2,3}, 22.52 )  ({1, 2,3, 4}, 22.52 ) (,1)  ({1},1)  ({1, 2},1)  ({1, 2,3},1)  ({1, 2,3, 4},1) (, 2)  ({1}, 2)  ({1, 2}, 2)  ({1, 2,3}, 2)  ({1, 2,3, 4}, 2) (, 22 )  ({1}, 22 )  ({1, 2}, 22 )  ({1, 2,3}, 22 )  ({1, 2,3, 4}, 22 ) (, 23 )  ({1}, 23 )  ({1, 2}, 23 )  ({1, 2,3}, 23 )  ({1, 2,3, 4}, 23 ) (, 23.5)  ({1}, 23.5)  ({1, 2}, 23.5)  ({1, 2,3}, 23.5)  ({1, 2,3, 4}, 23.5) (, 23.52 )  ({1}, 23.52 )  ({1, 2}, 23.52 )  ({1, 2,3}, 23.52 )  ({1, 2,3, 4}, 23.52 ) Sau khi “bóc” các lớp của các hình chữ nhật trên ta được một phân hoạch xích đối xứng của poset tích trực tiếp P ( S )  P(23.52 ) là : ({2, 4},1.52 )  ({2, 4}, 2.52 ) ({3, 4},1.52 )  ({3, 4}, 2.52 )