Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạm

Loại tài liệu: PDF

Số trang: 49 Trang

Tài liệu: ✅ ĐÃ ĐƯỢC PHÊ DUYỆT

TẢI VỀ

Nội dung chi tiết: Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn , HỮU HẠNLUẬN VĂN THẠC sỉ TOÁN HỌCThành phố Hồ Chi -Minh - 2010PHÀN MỞ ĐẢƯKe từ khi Spemer đưa ra định lý Spemer (1928) về số cưc đại các phần tú cúa

một phan xích trên poset các tập con của tập n-phân tử thi đị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ý t Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

huyế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

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

của nó. Vì trong các dạng poset, ta thường quan tâm đến các poset có hang 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

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn hà 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 Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

ưng kill 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

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

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á dẹp ; họ dưa ra dược một phàn hoạch trực tiếp xích đoi xứng

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn trực tiếp xích đối xứng poset P(m) VỚI m = p^p^—pn" • 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è trinh 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à chi ra răng c Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

ả hai phương pháp nãy đều như nhau. Sau dó. 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ề khia cạnh sổ lượng xích đối xứng, size

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

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 dung cúa phương pháp phân hoạch trực tiếp xích đối xứng

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn êu tfx.y.r r p la có:i)X < Xii)xx-yiii)xx

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 (posct):Định nghĩa 1.2.1:Tập hợp p với quan Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

hệ thứ lự < được gọi là một tập sắp thứ lu 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

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

ọ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 het.1.3.Một số khái niệm cơ ban trên một poset:Trong một poset

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,

Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn < J'.>Nêu X < V và không có z r p: X < z < y thì la nói r phũ X.r Nếu có duy nhất z p: z < X, Vx fe p thi ta gọi z là phần từ bé nhất cua p. kỷ hiệu l

ã 0.Ví dụ 1.3.1: I) Phần tư 0 cùa poset các tập con cua tập n phần tư s lá tập 0.I) Phần từ 0 cua poset các ước nguyên dương cua một số nguyên m là 1. Một số bài toán phân hoạch xích đối xứng trên các xích đối xứng trên các poset có hạn, hữu hạn

>X é p dược gọi là phần tư tối tiêu cùa p nếu không có y «= p: y < X.

^SPBỌ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG DẠI HỌC sứ PHẠM TP. HÒ CHÍ .MINHThân Thi Phuong TrangMỘT SÓ BÀI TOÁN PHÂN HOẠCH XÍCH ĐÓI XÚNG TRÊN CÁC POSET CÓ HẠNG,