Luận văn 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

  • Người chia sẻ :
  • Số trang : 49 trang
  • Lượt xem : 12
  • Lượt tải : 500
  • Tất cả luận văn được sưu tầm từ nhiều nguồn, chúng tôi không chịu trách nhiệm bản quyền nếu bạn sử dụng vào mục đích thương mại

NHẬP MÃ XÁC NHẬN ĐỂ TẢI LUẬN VĂN NÀY

Nếu bạn thấy thông báo hết nhiệm vụ vui lòng tải lại trang

Bạn đang xem trước 20 trang tài liệu Luận văn 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD LUẬN VĂN ở trên

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 ( k k k 1 2     . 1 n ) 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 p p p  1 2 k k 1 2 . . nkn , 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