Luận Văn: Bóng của Đoạn trong Multiset - Ứng Dụng Toán Học

Khám phá khóa luận về toán học bóng của một đoạn trong multiset. Nghiên cứu chuyên sâu về các tính chất và ứng dụng trong lĩnh vực liên quan.

• Tác giả: Phạm Văn Trí
• Người hướng dẫn: Ts. Trần Huyên
• Trường học: Trường Đại học Sư phạm Thành phố Hồ Chí Minh
• Chuyên ngành: Đại số
• Đề tài: Bóng Của Một Đoạn Trong Multiset
• Loại tài liệu: Khóa luận tốt nghiệp
• Năm xuất bản: 2012
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI MỞ ĐẦU
• 1. CHƯƠNG I: KIẾN THỨC CHUẨN BỊ
• 1.1. Poset:
• 1.2. Trội, trội trực tiếp:
• 1.3. Phần tử tối đại, tối tiểu:
• 1.4. Phần tử lớn nhất, phần tử nhỏ nhất:
• 1.5. Hàm hạng:
• 1.6. Mức:
• 1.7. Bóng:
• 1.8. Đoạn, đoạn đầu:
• 1.9. Thứ tự từ điển:
• 1.10. Sơ lược về lịch sử dẫn đến vấn đề:
• 2. CHƯƠNG II: BÓNG CỦA ĐOẠN TRONG MULTISET
• 2.1. Bóng của đoạn trong poset các tập con của tập đơn bội:
• 2.1.1. Từ tập con của tập đơn bội cho đến vector tọa độ:
• 2.1.2. Các kết quả chính:
• 2.2. Bóng của đoạn trong multiset:
• 3. CHƯƠNG III: NHỮNG ĐIỂM TƯƠNG ĐỒNG VÀ SAI KHÁC TRONG HAI TRƯỜNG HỢP TRÊN
• 3.1. Bóng của một đoạn đầu:
• 3.2. Bóng của đoạn mà hai đầu mút có tọa độ khác không đầu tiên là như nhau:
• 3.3. Bóng của đoạn mà hai đầu mút có tọa độ khác không đầu tiên là khác nhau:
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khám Phá Bóng của Đoạn trong Multiset Tổng quan Luận văn

Chủ đề bóng của đoạn trong multiset là một lĩnh vực chuyên sâu thuộc toán học rời rạc và lý thuyết tổ hợp. Luận văn này tập trung giải quyết một câu hỏi trung tâm: "Với những điều kiện cần và đủ nào thì bóng của một đoạn là một đoạn trong multiset?". Khái niệm "bóng của tập hợp" lần đầu được Sperner giới thiệu vào năm 1928, tạo ra một công cụ mạnh mẽ để giải quyết các bài toán extremal liên quan đến antichain. Sau đó, định lý Kruskal-Katona đã tổng quát hóa vấn đề, đưa ra phương pháp đánh giá cận dưới cho kích thước bóng của các tập con cùng lực lượng. Luận văn này mở rộng các khái niệm nền tảng đó từ môi trường tập hợp đơn bội (set) sang đa tập hợp (multiset), một cấu trúc phức tạp hơn nơi các phần tử có thể lặp lại. Việc nghiên cứu này không chỉ có giá trị lý thuyết mà còn mở ra những hướng tiếp cận mới cho các vấn đề liên quan đến cấu trúc tổ hợp và bất đẳng thức trong toán học. Nội dung chính của bài viết sẽ hệ thống hóa các kiến thức chuẩn bị, trình bày các kết quả chính trong cả hai môi trường tập đơn bội và đa bội, đồng thời so sánh những điểm tương đồng và khác biệt, cung cấp một cái nhìn toàn diện về bài toán bóng của đoạn trong multiset.

1.1. Lịch sử bài toán Từ Định lý Sperner đến Kruskal Katona

Lịch sử của khái niệm bóng của tập hợp gắn liền với những tên tuổi lớn trong lý thuyết tổ hợp. Năm 1928, Sperner đã sử dụng kỹ thuật này để chứng minh định lý nổi tiếng của mình về kích thước của các antichain. Công trình của ông đã đặt nền móng cho một nhánh quan trọng của toán học extremal. Vấn đề sau đó được phát triển một cách tự nhiên: tìm cận dưới lớn nhất cho kích thước của bóng. Đỉnh cao của hướng nghiên cứu này là Định lý Kruskal-Katona, được chứng minh độc lập bởi Kruskal (1963) và Katona (1968). Định lý này chỉ ra rằng để tối thiểu hóa kích thước bóng, ta nên chọn các tập hợp con đầu tiên theo một thứ tự tuyến tính cụ thể, thường là thứ tự từ điển. Kết quả này sau đó được Clements và Linstrom mở rộng cho poset các tập con của multiset, khẳng định rằng thứ tự từ điển vẫn giữ vai trò quan trọng trong việc xác định các tập hợp tối ưu. Luận văn kế thừa và phát triển các kết quả này, nhưng tập trung vào một thuộc tính cấu trúc khác: khi nào thì bóng của một đoạn (một tập hợp các phần tử liên tiếp) vẫn giữ được tính chất là một đoạn.

1.2. Phát biểu vấn đề cốt lõi trong lý thuyết tập hợp đa bội

Vấn đề trung tâm của luận văn là xác định các điều kiện cần và đủ để bóng của đoạn trong multiset vẫn là một đoạn. Một đoạn, ký hiệu là [a, b], là tập hợp tất cả các phần tử x nằm giữa a và b theo một thứ tự tuyến tính cho trước. Bóng của đoạn này, A[a, b], là tập hợp các phần tử "ngay dưới" các phần tử trong [a, b]. Trong khi bóng của một đoạn đầu (initial segment) luôn là một đoạn đầu, điều này không còn đúng với một đoạn bất kỳ. Cấu trúc tổ hợp của đa tập hợp phức tạp hơn nhiều so với tập đơn bội, do sự xuất hiện của các phần tử lặp lại. Điều này dẫn đến việc bóng có thể bị "phân mảnh" hoặc "không liên tục". Do đó, câu hỏi đặt ra không chỉ là về kích thước bóng mà còn về việc bảo toàn cấu trúc của nó. Luận văn giải quyết bài toán này bằng cách tiếp cận từng bước: trước hết là trong môi trường tập đơn bội, sau đó tổng quát hóa các phương pháp và kết quả cho đa tập hợp, nơi các bất đẳng thức tổ hợp và kỹ thuật chứng minh toán học trở nên phức tạp hơn.

II. Thách thức khi xác định bóng của đoạn trong đa tập hợp

Việc xác định cấu trúc của bóng của đoạn trong multiset đối mặt với nhiều thách thức đáng kể. Khác với tập hợp đơn giản, một đa tập hợp cho phép các phần tử lặp lại, làm cho không gian các tập con trở nên phong phú và phức tạp hơn. Khi chuyển từ không gian tập con sang biểu diễn vector, các tọa độ không còn bị giới hạn ở {0, 1} mà có thể nhận nhiều giá trị nguyên. Sự phức tạp này ảnh hưởng trực tiếp đến cấu trúc của bóng. Một trong những khó khăn chính là việc bóng của một đoạn không còn đảm bảo tính "liên tục". Có thể tồn tại những "khoảng trống" trong tập hợp bóng, khiến nó không còn là một đoạn theo thứ tự từ điển. Việc tìm ra các điều kiện chính xác trên hai đầu mút a và b của đoạn để đảm bảo tính liên tục của bóng là mục tiêu cốt lõi. Điều này đòi hỏi phải phân tích kỹ lưỡng mối quan hệ giữa các tọa độ của vector, đặc biệt là các tọa độ khác không đầu tiên và cuối cùng, để có thể đưa ra các chứng minh toán học chặt chẽ về việc bảo toàn cấu trúc tổ hợp này.

2.1. Sự phức tạp của cấu trúc đa tập hợp so với tập đơn bội

Sự khác biệt cơ bản giữa tập đơn bội và đa tập hợp nằm ở tính đa dạng của các tập con của multiset. Trong tập đơn bội S = {1, 2, ..., n}, mỗi tập con có thể được biểu diễn bằng một vector Boolean x có các thành phần x_i trong {0, 1}. Ngược lại, trong một đa tập hợp mà phần tử thứ i lặp lại k_i lần, tập con được biểu diễn bằng một vector nguyên x với 0 ≤ x_i ≤ k_i. Sự gia tăng bậc tự do này làm cho số lượng và cấu trúc của các tập con trở nên phức tạp hơn rất nhiều. Thứ tự bao hàm và các quan hệ trội trong poset của đa tập hợp cũng đa dạng hơn. Do đó, các định lý và kết quả từ tập đơn bội không thể áp dụng trực tiếp mà cần được điều chỉnh hoặc chứng minh lại một cách cẩn thận. Ví dụ, khái niệm hệ số nhị thức tổng quát thay thế cho hệ số nhị thức thông thường khi đếm số tập con có cùng kích thước.

2.2. Khó khăn trong việc tìm chặn trên và chặn dưới kích thước bóng

Mặc dù luận văn tập trung vào cấu trúc, vấn đề kích thước bóng vẫn là một nền tảng quan trọng. Trong lý thuyết tổ hợp, các bài toán extremal thường yêu cầu tìm chặn trên và chặn dưới cho một tham số nào đó. Định lý Kruskal-Katona cung cấp một chặn dưới chặt chẽ cho kích thước bóng của một họ các tập con có cùng kích thước. Tuy nhiên, khi xét một đoạn thay vì một đoạn đầu, việc xác định kích thước bóng trở nên khó hơn. Kích thước này phụ thuộc vào vị trí tương đối của hai đầu mút a và b trong thứ tự từ điển. Phân tích này đòi hỏi các công cụ tinh vi hơn là chỉ áp dụng định lý một cách máy móc. Các bất đẳng thức tổ hợp phải được xây dựng dựa trên cấu trúc cụ thể của đoạn, và việc chứng minh chúng đòi hỏi sự hiểu biết sâu sắc về cách các phần tử trong đoạn tạo ra bóng của chúng.

III. Phương pháp tiếp cận Phân tích bóng trong tập đơn bội

Để giải quyết bài toán phức tạp về bóng của đoạn trong multiset, luận văn áp dụng một phương pháp tiếp cận kinh điển trong toán học: giải quyết một trường hợp đặc biệt đơn giản trước. Cụ thể, nghiên cứu bắt đầu với việc phân tích bóng của đoạn trong poset các tập con của một tập đơn bội. Đây là một trường hợp đặc biệt của đa tập hợp nơi mỗi phần tử chỉ lặp lại một lần. Cách tiếp cận này cho phép làm quen với các ký hiệu, định nghĩa và kỹ thuật cơ bản trong một môi trường quen thuộc hơn. Mỗi tập con được đồng nhất với một vector tọa độ Boolean (chỉ chứa 0 và 1). Luận văn trình bày một loạt các bổ đề và định lý, cung cấp các điều kiện cần và đủ để bóng của một đoạn [a, b] là một đoạn. Các điều kiện này phụ thuộc chặt chẽ vào vị trí tương đối của các chỉ số khác không trong vector a và b. Đây là bước đệm quan trọng, vì các kỹ thuật và ý tưởng phát triển ở đây sẽ được tổng quát hóa cho trường hợp đa tập hợp trong phần tiếp theo. Đây là một ví dụ điển hình của chứng minh toán học có cấu trúc.

3.1. Kỹ thuật vector hóa và thứ tự từ điển trong toán học rời rạc

Một kỹ thuật nền tảng trong luận văn là việc chuyển đổi từ lý thuyết tập hợp sang đại số tuyến tính thông qua vector hóa. Mỗi tập con A của tập S = {p₁, p₂, ..., pₙ} được biểu diễn bằng một vector x = (x₁, x₂, ..., xₙ), trong đó xᵢ = 1 nếu pᵢ ∈ A và xᵢ = 0 nếu ngược lại. Phép đồng nhất này cho phép chuyển quan hệ bao hàm tập hợp (⊆) thành quan hệ thứ tự tự nhiên trên các vector. Để giải quyết các bài toán extremal, người ta thường trang bị thêm cho không gian vector một thứ tự tuyến tính, và thứ tự từ điển (lexicographical order) là một lựa chọn phổ biến và hiệu quả. Thứ tự này sắp xếp các vector như cách các từ được sắp xếp trong từ điển. Kỹ thuật này giúp biến một tập hợp các đối tượng tổ hợp thành một dãy có thứ tự, cho phép xác định các khái niệm như "đoạn" và "đoạn đầu" một cách chặt chẽ.

3.2. Các định lý chính về điều kiện để bóng là một đoạn Tập đơn bội

Trong môi trường tập đơn bội, luận văn đã chứng minh các định lý quan trọng xác định khi nào bóng của đoạn A[a, b] là một đoạn. Kết quả phụ thuộc vào chỉ số i và j của thành phần '1' đầu tiên trong vector a và b. Ví dụ, Định lý 1 chỉ ra rằng nếu i > j + 1, thì A[a, b] là một đoạn đầu IS(A"b). Định lý 2 xử lý trường hợp i = j, chỉ ra rằng A[a, b] là một đoạn khi và chỉ khi b là phần tử lớn nhất có thể và a có một cấu trúc đặc biệt. Định lý 3 giải quyết trường hợp phức tạp nhất khi i và j gần nhau. Các chứng minh toán học này sử dụng phương pháp phân tích cấu trúc của các vector trong đoạn và cách chúng tạo ra các phần tử trong bóng, cho thấy tầm quan trọng của việc lựa chọn các đầu mút của đoạn.

IV. Giải pháp cho Multiset Các mệnh đề và chứng minh toán học

Sau khi xây dựng nền tảng vững chắc từ trường hợp tập đơn bội, luận văn tiến vào giải quyết vấn đề chính: bóng của đoạn trong multiset. Phương pháp tiếp cận được tổng quát hóa, trong đó các tập con được biểu diễn bằng vector nguyên thay vì vector Boolean. Một kỹ thuật quan trọng là phân tích tập hợp bóng A[a, b] thành hai bộ phận: A'[a, b] (bóng được tạo ra bằng cách giảm tọa độ khác không đầu tiên) và A''[a, b] (phần còn lại). Luận văn chứng minh rằng A'[a, b] luôn là một đoạn. Do đó, vấn đề cốt lõi là xác định khi nào A''[a, b] cũng là một đoạn và khi nào hai phần này kết hợp với nhau một cách "liền mạch". Các mệnh đề chính đưa ra các điều kiện cần và đủ cho việc này. Ví dụ, Mệnh đề 2 chỉ ra rằng bóng của đoạn trong multiset A[a, b] là một đoạn khi và chỉ khi b có dạng zaᵢh...(k-aᵢ)z (phần tử lớn nhất có thể) và tồn tại một phần tử a* trong đoạn [a, b] sao cho bóng của nó tạo ra phần tử nhỏ nhất cần thiết để "lấp đầy khoảng trống".

4.1. Phân tích bóng thành phần và vai trò của tọa độ khác không

Trong trường hợp đa tập hợp, khi hai đầu mút a và b có cùng tọa độ khác không đầu tiên (ví dụ a = zaᵢu và b = zaᵢv), bóng của một phần tử x trong đoạn có thể được tạo ra theo hai cách: giảm tọa độ xᵢ hoặc giảm một tọa độ xⱼ nào đó với j > i. Điều này dẫn đến sự phân tách tự nhiên của bóng A[a, b] thành hai tập con A'[a, b] và A''[a, b]. A'[a, b] chứa các bóng được tạo bởi việc giảm tọa độ aᵢ, trong khi A''[a, b] chứa các bóng còn lại. Luận văn chứng minh một kết quả quan trọng: A'[a, b] luôn là một đoạn. Vai trò của tọa độ khác không đầu tiên là cực kỳ quan trọng, nó quyết định cấu trúc cơ bản của một phần của tập hợp bóng. Thách thức còn lại là phân tích A''[a, b] và sự kết nối giữa hai tập này.

4.2. Mệnh đề cốt lõi Điều kiện cần và đủ cho bóng của đoạn

Mệnh đề 2 của luận văn là một trong những kết quả trung tâm, cung cấp điều kiện cần và đủ để bóng của đoạn trong multiset là một đoạn (khi các đầu mút có cùng tọa độ khác không đầu tiên). Điều kiện bao gồm hai phần: (1) Đầu mút b phải là phần tử "lớn nhất có thể" trong lớp của nó. (2) Phải tồn tại một phần tử a* trong đoạn [a, b] sao cho bóng của nó (tạo bởi tọa độ sau tọa độ đầu tiên) chính là phần tử nhỏ nhất của A''[a,b], và phần tử này phải là trội trực tiếp của phần tử lớn nhất trong A'[a,b]. Về cơ bản, điều kiện này đảm bảo không có "khoảng trống" giữa hai tập bóng thành phần A' và A''. Chứng minh toán học cho mệnh đề này dựa trên việc phân tích cấu trúc của các phần tử và sử dụng các kết quả về đoạn đầu.

V. Ý nghĩa lý thuyết và ứng dụng tiềm năng của luận văn

Mặc dù mang tính lý thuyết cao, các kết quả về bóng của đoạn trong multiset có ý nghĩa quan trọng trong nhiều lĩnh vực của toán học rời rạc. Việc hiểu rõ khi nào một cấu trúc tổ hợp được bảo toàn qua một phép toán (như phép lấy bóng) là nền tảng cho việc giải quyết các bài toán extremal phức tạp hơn. Các điều kiện được tìm thấy trong luận văn có thể được sử dụng để xây dựng các họ tập hợp có cấu trúc đặc biệt, phục vụ cho việc kiểm tra các giả thuyết hoặc xây dựng các phản ví dụ. Về mặt ứng dụng, các khái niệm trong lý thuyết tổ hợp như bóng và antichain có mối liên hệ với các lĩnh vực như lý thuyết mã hóa (thiết kế mã sửa lỗi), tối ưu hóa tổ hợp và thiết kế thuật toán tổ hợp. Ví dụ, các bất đẳng thức liên quan đến kích thước bóng, như bất đẳng thức tổ hợp Kruskal-Katona, được dùng để chứng minh các giới hạn về hiệu suất của các thuật toán hoặc mã hóa. Nghiên cứu này đóng góp vào kho tàng kiến thức cơ bản, làm tiền đề cho các ứng dụng tiềm năng trong tương lai.

5.1. Đóng góp cho các bài toán tối ưu hóa và lý thuyết mã hóa

Trong tối ưu hóa tổ hợp, nhiều bài toán có thể được mô hình hóa trên các poset. Việc hiểu cấu trúc của các tập con và bóng của chúng giúp thiết kế các thuật toán tổ hợp hiệu quả hơn. Ví dụ, việc biết được khi nào một tập hợp các giải pháp (một đoạn) tạo ra một tập hợp "lân cận" (bóng) có cấu trúc tốt có thể giúp đơn giản hóa không gian tìm kiếm. Trong lý thuyết mã hóa, các từ mã có thể được xem như các phần tử của một poset. Các điều kiện về khoảng cách giữa các từ mã, một yếu tố quan trọng để sửa lỗi, có liên quan đến các khái niệm như antichain và bóng. Các kết quả chi tiết về cấu trúc của bóng của đoạn có thể cung cấp những hiểu biết mới cho việc thiết kế các loại mã đặc biệt trên đa tập hợp.

5.2. Đóng góp chính của luận văn cho lý thuyết tập hợp đa bội

Đóng góp chính của luận văn là đã giải quyết một cách trọn vẹn câu hỏi về điều kiện để bóng của đoạn trong multiset là một đoạn, ít nhất là trong trường hợp các đầu mút có cùng tọa độ khác không đầu tiên. Luận văn đã tổng quát hóa thành công các kết quả từ tập đơn bội sang môi trường đa tập hợp, một bước đi không hề tầm thường. Nó cung cấp các chứng minh toán học chi tiết và chặt chẽ, làm phong phú thêm hiểu biết về cấu trúc tổ hợp của poset các tập con của multiset. Hơn nữa, việc so sánh hai trường hợp trong Chương III đã làm rõ những điểm tương đồng và khác biệt, cho thấy kết quả trong tập đơn bội thực sự là một trường hợp đặc biệt của kết quả tổng quát hơn, khẳng định tính nhất quán của lý thuyết.

Trích đoạn nội dung tài liệu

CHƯƠNG I: KIÊN THỨC CHUAN BỊ,.--- 2-52 52SE‡EE‡EE2EE2EEEEEEEEErrrrerree 6 I.- - --- << 11191199 11119111 HH HH 6 II. Đoạn, đoạn đầu:. Thứ tự từ điỂn: .------ 2 2+2E+EE2EE2E2E12112112112112112112117171 1111111111 xe 10 VII. So lược về lich sử dẫn đến vấn G6: .cecececcsececcssssecesecsesesesececsesesecseseeveeeeeees 10 CHUONG II: BONG CUA DOAN TRONG MULTISET.

Bóng của đoạn trong poset các tập con của tap đơn bội:. Từ tập con của tập đơn bội cho đến vector tọa đỘ:. Các kết quả chính:. ---- ¿+ SE ©E9EE£EE£EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEkrrkrrerree l6 2.

Bóng của đoạn trong multiset:. -- -- - c+S+E£SE#EE#EEEEEEEEEEEEEEEEEEEEEE11111111111 1.----- St tt SE EEE197101111111111111111 1111111111 xe.- --¿- ¿+ ©E+SE+E£EE#EE£EEEEEEEEEEEEEE111211111111111 11111111 ExU 35 CHUONG III: NHỮNG DIEM TƯƠNG DONG VÀ SAI KHAC TRONG HAI TRƯỜNG HOP TREN. Bóng của một đoạn đầU:. Bóng của đoạn mà hai đầu mút có tọa độ khác không đầu tiên là như nhau:.

Bóng của đoạn mà hai đầu mút có tọa độ khác không đầu tiên là khác nhau:45 TÀI LIEU THAM KHẢO .--2¿22- 2 5S£2S£22+£EEEEE2EEEEEEEEEzEEerxerxerrrrrxervree 46 Bóng của đoạn trong Multiset Luân văn tốt nghiệp đạt học CHUONG I: KIÊN THỨC CHUAN BỊ I. Poset: Poset là một tập hợp với thứ tự bộ phận, tic =(Š,<) với < là một thứ tự bộ phận trên S$.1: (N’,|) là một poset. That vay: Vx € N’, tacé x1 x ( thỏa tính phản xa). alb Gia sử: bla b=k > “= a = lka = Ik =1=> => a=b ( thỏa tính phan xứng).

a=Ib k=1 alb b=ka na Giả sử > =>c=lka= alc ( thỏa tính bắc câu). blc c=lb Và rõ ràng quan hệ ước số "|" là thứ tự bộ phận. Vậy (ÑÏ,Ù là một poset.Ì) không là poset vì không thỏa tính chất phan xứng. : ,„ |2l-=2 Chang hạn lây 212 nhưng —2 # 2.3: Gọi P(S) là tập hợp chứa tat cả các tập con của S.

Và C là thứ tự bao hàm thì (P(S),C) là một poset. Thật vậy: AC A,VAe P(S) (phan xa). Bóng của đoạn trong Multiset Luân văn tốt nghiệp đạt học ia sử >A= an xứng). BcA P ` AcB yy Giả sử 4 => ACC (bac câu).

BcC Và rõ ràng quan hệ bao hàm là quan hệ thứ tự bộ phận. Vậy (P(S),C) là một poset. Trội, trội trực tiếp: Xét Poset (S,<) và x,yeS. 1) Nếu x < y thì ta nói y là trội của x hay x được trội bởi y.

ii) Ta nói y là trội trực tiếp của x nếu y trội x và không ton tại z # x, y sao cho: x< Z< y. Phan tử toi dai, toi tiéu: Trong poset (S,<), một phan tử m được gọi là tối đại (tương ứng là tối tiêu) nếu m không có trội thực sự ( tương ứng không là trội thực sự của phần tử nào cả). Phan tử lén nhất, phan tử nhỏ nhất: Trong poset (Š,<), được gọi là phan tử lớn nhất (tương ứng nhỏ nhất) nếu : x<,Vx€ Š (tương ứng ax x,VxeES).1: Poset (P(S),C) có phần tử nhỏ nhất là @, phan tử lớn nhất là ,Š. Bong của đoan trong Mulltiset Luận văn tot nghiệp dai hoc Poset (N*1) có phan tử nhỏ nhất là 1.

s* Lưu ý: Trong | poset, phan tử lớn nhất nêu tôn tại là phan tử tối đại duy nhất (tương tự cho phan tử nhỏ nhất và tối tiểu). Trong 1 poset hữu hạn, nêu có duy nhất phan tử tối đại thi đó là phan tử lớn nhất (tương tự cho phân tử nhỏ nhất và tối tiêu). Hàm hạng: Cho poset P = (§,<), giả sử có 1 ánh xạ r từ poset P vào N sao cho: r(a) =0 nếu a là phan tử tối tiểu của P, Và r{b) =r(a) +1 nếu Ð là trội trực tiếp của a. Thi r được gọi là hàm hạng của P.

Khi đó, P cũng được gọi là 1 poset có hạng. Mức: Cho poset = (§,<) có hàm hạng r. Ta định nghĩa mức thứ & của P là: P. Bong: Cho P là một poset có hạng với các mức P,P.

bóng của # được định nghĩa là: Aa ={x € P_,:a là trội trực tiếp của x} Và bóng của AC P, là: AA = U Aa “GA Sau đây là một số Ví dụ về poset có hạng mà ta sẽ dùng đến trong các phan kể tiếp. Như thông lệ, ta ký hiệu lA| chỉ số phan từ của A. Và dé đơn giản ký hiệu, vector (x,.X,) được viet là x,x;.X, nêu không có gì nhầm lần. Bong của đoan trong Mulltiset Luận văn tot nghiệp dai hoc Ví dụ 4.1: Poset (P(S),<), với P(S) là tập hợp các tập con của Š = {1,2,.,7} là một poset có hạng với các đặc trưng: Phan tử: a là tập con của S.

Thứ tự bộ phận: a Cb. Hàm hạng: r(a) = la| là số phan tử của a. Mức thứ k: P,(Š) ={a cS :|a| =k}.,k, )cdc tập con của tập đa bội gồm nm phan tử, trong đó phan tử thứ i lặp k, lần trong đó k, <k, <.< k„„k, EN’, với quan hệ "<" là một poset có hạng với các đặc trưng sau: Phan tử: x = x,x,.%, với OS x, $k,,x, EN” Thứ tự bộ phận: với X = 1,X;.V„ thì xS<y€©x,<y,,Vi =Ì],. Hàm hạng: r(x) = xX, +X, +.%, EP, : Trước hết ta định nghĩa bóng thành phan thứ 7 của x là: A.

Thì: Ax =VA,x Vi du 4.3: Poset B cac vector Bool Phan tử: x = x,x¿. P » ° a = £ oa e Bong của đoan trong Multiset Luận văn tot nghiệp dai hoc Thứ tự bộ phận: với X=X,1;.V„ thi x<y nêu k<Sn và i, <<.- = ý, Hàm hạng: Với x = x,x,. ={xeB: dimx=k}, PR, ={@}.%, € P: Gọi Á,x là vector có được bằng cách bỏ đi x, thì: Avx={A,x,l< j Sn}. Doan, đoạn đầu: Cho poset có hạng , trên mức mỗi mức Fes ta trang bị thêm một thứ tự tuyên tính "<”, với a,b e F¿.

ta định nghĩa: Đoạn [a;b]={x € ,:a<x<b}, và Doan đầu xác định bởi a là: /S(đ)={x€P,:x<4)} VI. Thứ tự từ điền: Cho a=a,a,.b, ta nói a < b nếu Js € N,1 <5 <1 sao cho: a,=b,,t<s và a <b,. Sơ lược về lịch sử dan đến vẫn đề: Chúng ta ký hiệu n ]-e nêu nek oa k J-° neun<k. n k Từ năm 1928, Sperner đã chứng minh rang : Nếu AC P,(S) với § = {I,2.

thì ta có: al > ; n n ial Vấn đề tự nhiên đặt ra là tìm cận dưới lớn nhất của | AA]. Bong của đoan trong Multiset Luận văn tot nghiệp dai hoc Một cách tông quát, với P. là mức thử & của poset có hạng P và me Ñ cho trước, tìm A C 2 sao cho [A =m va: |AA| = min{|AB|: 8 c P,.|B| =m} Đề giải quyết bài toán này, thường người ta tìm một thứ tự toàn phan trên F, mà ta gọi là thứ tự tuyén tính và chứng minh rằng tap A phải tìm gôm m phần tử đầu tiên của P. trong thứ tự tuyến tính ấy.

Đó là nội dung chủ yếu của định lý Kruskal-Katona. Và về sau, Clements — Linstrom đã mở rộng thêm định lý KK cho poset S(k,,k,,.,k,) các tập con của tập đa bội. Nói chung, Clements — Linstrom đã chứng minh được rang với thứ tự tuyến tính là thứ tự từ điển thì S(k,,k,.k,„) là một K-poset. Chúng ta không đi sâu vào việc tim hiệu K-poset.

Nói riêng, họ đã chỉ ra rằng bóng của một đoạn đầu xác định bởi phần tử a trong S, theo thứ tự từ điện lại là một đoạn đầu trong S593 Van dé được đặt ra là: Những đặc trưng nao của một số các tập con của | poset thì còn giữ lại được qua bóng ? Luận văn này nhằm giải quyết một phan rất nhỏ của van đề trên: Với những điều kiện nào thì bóng của một đoạn lại là một đoạn trong multiset 2 Đề giải quyết van dé trên, trước tiên ta hệ thống lại một vài khái niệm và đưa ra một số ký hiệu như sau: Cho poset S$(k,,k,,.,k,,) các tập con của tập đa bội phần tử mà phan tử thứ i lặp É, lan. Bong của đoan trong Mulltiset Luận văn tot nghiệp dai hoc Như trên đã đề cập, các tập con có thể đồng nhất với các vector nguyên x=x,x;.v„ mà OS x, Sk, với mỗi i. Thứ tự bao hàm của các tập con chuyên sang các vector cho ta thứ tự tự nhiên sau: X=x,1;.V„ khi và chỉ khi x, S Y, với mọi ï. Khái niệm hạng, mức, bóng của một phần tử, một tập hợp được đỉnh nghĩa và ky hiệu như Ví dụ 4.

Đề giải quyết van dé đặt ra, ta trang bị thêm một thứ tự tuyền tính là thứ tự từ điền. Về sau, ta chủ yếu dùng thứ tự này. Dé tiện lợi cho sư trình bày, trước hết ta cần thống nhất một số ký hiệu: Với mỗi phan trae S, ma tọa độ khác không đầu tiên là a,, ta có thé viết: q = £q,t, ở đây z =Ô.4 a’ Nếu toa độ khác không cuối cùng của a là đ, thi ta viết: đ = Vđ,Z. A”a=max{A,a} Đối với các bóng thành phan của a, ta ký hiệu: 4ˆ : Aa=mmn{A,z} tong A”a = za,u(a, —1)z De thay: neu d = zajua,z thi) : Na = z(a, —])ua,z Đối với số tự nhiên m < k, ta ký hiệu: h,(m) = max{x = zx,t :|x|= m,,x, # 0} Ï (m) = min{x = vx,z :|.x| =m,x, #0} h(m) = max{x:xeS_} Nói riêng:.

: L(m) = min{x: x € S„} Bong của đoan trong Multiset Luận văn tot nghiệp dai hoc Bây giờ. ta xét bóng A[a;b] mà a,b có tọa độ khác 0 đầu tiên là như nhau, tức là a = za và b = za,v. Ta phân tích A[a;b] thành hai bộ phận được ký hiệu như sau: (ey = A[a;b]\Al[a;b]={za,w: za.u' € A[a;b]} A'[a;b] ={A'x: x e[a;b]} ={z(a, —Du: za,u e[a;b]} CHUONG II: BONG CUA DOAN TRONG MULTISET Bong của đoan trong Mulltiset Luận văn tot nghiệp dai hoc Trước khi xem xét bóng của một đoạn trong multset, ta xem xét bóng của một đoạn trong poset các tập con của tập đơn bội. và xem đây là một trường hợp đặc biệt cua poset các tập con của tập đa bội (multiset).

Đây được xem là phần tương đối quan trọng của bài luận văn vì nó cho phép người đọc tiếp cận và làm quen với những gì cơ bản nhất từ ký hiệu cho đến ý nghĩa của một số kiến thức phải dùng sau này. Bóng của đoạn trong poset các tập con của tập đơn bội: 1. Từ tập con của tập đơn bội cho đến vector toa độ: Cho tập đơn bội S = { P¡, Ð;. D„ } Khi đó: ACS & (Vp, € A> p, €S) Gọi x, là số lần xuất hiện của các p, trong A thì rõ ràng x, € {0,1}.

Từ đó, quan hệ tập con này có thé được chuyền thành quan hệ ước số như sau: ACS có thê biểu diễn thành a = p;" Ø?. 0 nếup,£A Với xX, = : 1 ` nềup,eA Tương tự, lay B C 8, ta cũng biểu diễn thành: b=b= W Ị „ 3 2 y , 4: p;'p;’.