Luận văn thạc sĩ về lục giác lồi rỗng và bài toán Erdős-Szekeres

Luận văn thạc sĩ nghiên cứu hus về lục giác lồi rỗng, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Nguyễn Giang Thành
• Người hướng dẫn: PGS. Tạ Duy Phượng
• Trường học: Trường đại học khoa học tự nhiên, đại học quốc gia hà nội
• Chuyên ngành: Toán học
• Đề tài: Về Lục Giác Lồi Rỗng
• Loại tài liệu: Luận văn thạc sỹ
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN ERDÖS VỀ ĐA GIÁC LỒI RỖNG
• 1.1. Bài toán 1
• 1.1.1. Bài toán 1a Tồn tại hay không tồn tại số ES(n)?
• 1.1.2. Bài toán 1b Nếu số ES(n) tồn tại thì xác định ES(n) như một hàm của n
• 2. CHƯƠNG 2: CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ
• 2.1. Lược đồ chứng minh
• 2.2. Các trường hợp đơn giản
• 2.2.1. Các trường hợp (3, ≥ 0) và (≥ 6, 3)
• 2.2.2. Các trường hợp (3, ≥ 0) và (8,3)
• 2.2.3. Các trường hợp (6,3) và (7,3)
• 2.2.4. Các trường hợp (4, ≥ 0) và (≥ 7, 4)
• 2.2.5. Các trường hợp (5, 0) và (≥ 7, 5, 0)
• 2.2.5.1. Các trường hợp (5, 0) và (8, 5, 0)
• 2.2.5.2. Trường hợp (7, 5, 0)
• 2.2.6. Các trường hợp riêng
• 2.2.6.1. Trường hợp (5,1)
• 2.2.6.2. Trường hợp (6,1)
• 2.2.6.3. Các trường hợp (6,2) và (7,1)
• 2.2.7. Các trường hợp (5, ≥ 2)
• 2.2.8. Một quan sát cơ bản
• 2.2.9. Các trường hợp (5, ≥ 2)
• 2.2.10. Các trường hợp (6, ≥ 4)
• 2.2.11. Các trường hợp (≥ 7, ≥ 5, ≥ 1)
• 2.2.12. Ứng dụng của Quy tắc 1 và 2
• 2.2.13. Ứng dụng các Quy tắc 1-3
• 2.2.14. Trường hợp (1, 1, 1, 1, 1, 1, 1)
• 2.2.15. Trường hợp (1, 1, 1, 1, 1, 1, 1, 0)
• 2.2.16. Trường hợp (1, 1, 1, 1, 1, 1, 1, 1)
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về lục giác lồi rỗng trong toán học

Lục giác lồi rỗng là một khái niệm quan trọng trong hình học tổ hợp, liên quan đến bài toán Erdős về đa giác lồi rỗng. Khái niệm này không chỉ đơn thuần là một cấu trúc hình học mà còn chứa đựng nhiều vấn đề lý thuyết sâu sắc. Nghiên cứu về lục giác lồi rỗng giúp hiểu rõ hơn về các tính chất của đa giác lồi và các ứng dụng của nó trong toán học. Đặc biệt, bài toán Erdős-Szekeres đã mở ra nhiều hướng nghiên cứu mới trong lĩnh vực này.

1.1. Khái niệm lục giác lồi và lục giác rỗng

Lục giác lồi là một đa giác có sáu đỉnh, trong đó mọi góc đều nhỏ hơn 180 độ. Ngược lại, lục giác rỗng là lục giác không chứa bất kỳ điểm nào trong tập hợp điểm đã cho. Việc phân biệt giữa lục giác lồi và lục giác rỗng là rất quan trọng trong việc giải quyết các bài toán hình học tổ hợp.

1.2. Lịch sử nghiên cứu về lục giác lồi rỗng

Bài toán Erdős về lục giác lồi rỗng đã được phát biểu lần đầu vào năm 1978. Kể từ đó, nhiều nhà toán học đã tham gia nghiên cứu và đưa ra các kết quả quan trọng. Năm 2006, Szekeres và Peters đã chứng minh rằng E(6) tồn tại, mở ra một chương mới trong nghiên cứu lục giác lồi rỗng.

II. Vấn đề và thách thức trong nghiên cứu lục giác lồi rỗng

Mặc dù đã có nhiều tiến bộ trong nghiên cứu lục giác lồi rỗng, nhưng vẫn còn nhiều vấn đề chưa được giải quyết. Một trong những thách thức lớn nhất là xác định số nguyên dương nhỏ nhất E(n) cho mọi n. Điều này không chỉ đòi hỏi kiến thức sâu rộng về hình học tổ hợp mà còn cần đến các phương pháp toán học hiện đại.

2.1. Thách thức trong việc xác định E n

Việc xác định E(n) cho n = 6 vẫn là một bài toán mở. Mặc dù có nhiều giả thuyết và đánh giá, nhưng chưa có chứng minh chính thức nào cho thấy E(6) = 30. Điều này tạo ra một thách thức lớn cho các nhà nghiên cứu trong lĩnh vực này.

2.2. Các phương pháp nghiên cứu hiện tại

Nhiều phương pháp đã được áp dụng để nghiên cứu lục giác lồi rỗng, bao gồm các kỹ thuật hình học, lý thuyết đồ thị và các phương pháp tính toán. Những phương pháp này không chỉ giúp giải quyết các bài toán cụ thể mà còn mở rộng hiểu biết về các tính chất của lục giác lồi.

III. Phương pháp chứng minh E 6 ES 9

Chứng minh rằng E(6) ≤ ES(9) là một trong những bước quan trọng trong nghiên cứu lục giác lồi rỗng. Phương pháp này không chỉ dựa vào các lý thuyết hình học mà còn sử dụng các công cụ toán học hiện đại để đạt được kết quả chính xác.

3.1. Các bước chứng minh cơ bản

Chứng minh bắt đầu bằng việc xác định các cấu hình điểm trên mặt phẳng. Sau đó, áp dụng các định lý hình học để chứng minh rằng từ một tập hợp điểm đủ lớn, có thể chọn ra n điểm tạo thành một lục giác lồi rỗng.

3.2. Ứng dụng của các định lý hình học

Nhiều định lý hình học đã được áp dụng trong quá trình chứng minh, bao gồm định lý Ramsey và các định lý về bao lồi. Những định lý này cung cấp cơ sở lý thuyết vững chắc cho các kết quả đạt được.

IV. Ứng dụng thực tiễn của lục giác lồi rỗng

Lục giác lồi rỗng không chỉ có ý nghĩa lý thuyết mà còn có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Từ khoa học máy tính đến thiết kế đồ họa, các khái niệm liên quan đến lục giác lồi rỗng đã được áp dụng để giải quyết nhiều vấn đề thực tiễn.

4.1. Ứng dụng trong khoa học máy tính

Trong khoa học máy tính, các thuật toán dựa trên lục giác lồi rỗng được sử dụng để tối ưu hóa các bài toán phân tích dữ liệu và xử lý hình ảnh. Những ứng dụng này cho thấy tầm quan trọng của lục giác lồi rỗng trong công nghệ hiện đại.

4.2. Ứng dụng trong thiết kế đồ họa

Trong thiết kế đồ họa, lục giác lồi rỗng được sử dụng để tạo ra các mô hình hình học phức tạp. Việc áp dụng các khái niệm này giúp các nhà thiết kế tạo ra các sản phẩm sáng tạo và độc đáo.

V. Kết luận và tương lai của nghiên cứu lục giác lồi rỗng

Nghiên cứu về lục giác lồi rỗng vẫn đang tiếp tục phát triển với nhiều hướng đi mới. Các nhà toán học đang nỗ lực để giải quyết các vấn đề còn tồn đọng và mở rộng hiểu biết về các tính chất của lục giác lồi. Tương lai của nghiên cứu này hứa hẹn sẽ mang lại nhiều khám phá thú vị.

5.1. Tương lai của bài toán Erdo s Szekeres

Bài toán Erdős-Szekeres vẫn là một trong những bài toán mở quan trọng trong hình học tổ hợp. Nhiều nhà nghiên cứu đang tìm kiếm các phương pháp mới để giải quyết bài toán này, với hy vọng sẽ đạt được những kết quả đáng kể trong tương lai.

5.2. Khuyến khích nghiên cứu thêm

Việc khuyến khích các nghiên cứu mới trong lĩnh vực lục giác lồi rỗng là rất cần thiết. Các nhà toán học trẻ nên được khuyến khích tham gia vào các nghiên cứu này để đóng góp vào sự phát triển của lĩnh vực hình học tổ hợp.

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

Chương 1 TỔNG QUAN VỀ BÀI TOÁN ERDÖS VỀ ĐA GIÁC LỒI RỖNG 1.1 Bài toán 1 Với mỗi số tự nhiên n ≥ 3 , hãy xác định số nguyên dương nhỏ nhất ES(n) sao cho mọi tập tạo thành từ tối thiểu ES(n) điểm trên mặt phẳng ở vị trí tổng quát phải chứa n điểm là đỉnh của một đa giác lồi. Bài toán 1 được phát biểu vào năm 1935 và sau này được gọi là Bài toán Erdös- Szekeres. Erdös đã gọi bài toán này là bài toán có kết hạnh phúc (happy end problem hay happy ending problem), vì không lâu sau khi bài báo được in ra (1935), György Szekeres và Esther Klein đã tổ chức đám cưới (1937) và sống hạnh phúc bên nhau 60 năm. Bài toán 1 đã được tách ra thành hai bài toán: 1.1 Bài toán 1a Tồn tại hay không tồn tại số ES(n)? 1.2 Bài toán 1b Nếu số ES(n) tồn tại thì xác định ES(n) như một hàm của n.

Sự tồn tại số ES(n) có thể được chứng minh bằng hai cách. Cách thứ nhất do Szekeres chứng minh không lâu sau khi E. Klein phát biểu bài toán, dựa trên định lí Ramsey (mà Ông đã tự tìm lại do không biết định lí này). Từ đó ta có bất đẳng thức ES(n) ≤ R4 (n, 5) , trong đó R4 (n, 5) là số Ramsey.

Tuy nhiên, đánh giá này là quá lớn so với thực tế. Thí dụ, với n = 5 thì ES(5) ≤ 210000 quá xa so với ES(5) = 9. Cách thứ hai do Erdös chứng minh dựa trên một số quan sát hình học và kết 2n−4 quả ta được một đánh giá tốt hơn ES(n) ≤ Cn−2 + 1. Như vậy, bài toán 1a đã được trả lời khẳng định.

5 LUAN VAN CHAT LUONG download : add [e-mail] Rõ ràng ba điểm không thẳng hàng là đủ để tạo ra một tam giác nên ES(3) = 3. Dưới đây ta xét một số trường hợp cụ thể của bài toán với n = 4, 5, 6. Klein) Từ năm điểm bất kỳ trên mặt phẳng ở vị trí tổng quát bao giờ cũng chọn được bốn điểm là đỉnh của một tứ giác lồi. Đây cũng kết quả cho bài toán 1 trong trường hợp n = 4.

Bài toán đã được E.Klein chứng minh vào năm 1932. Chứng minh Trước tiên ta nhận thấy, tồn tại bốn điểm không tạo thành một tứ giác lồi (Hình 1.1 Vậy số điểm mà từ đó có thể tạo thành tứ giác lồi phải không ít hơn 5. Xét bao lồi của năm điểm (tập lồi nhỏ nhất chứa năm điểm đã cho) ở vị trí tổng quát. Chỉ có ba khả năng khác nhau sau đây.

• Khả năng 1 (Hình 1.2 Bao lồi của năm điểm là một ngũ giác ABCDE. Khi ấy mọi bộ bốn điểm từ năm điểm ấy đều tạo thành tứ giác lồi (và điểm còn lại nằm ngoài tứ giác lồi đó). Trong 6 LUAN VAN CHAT LUONG download : add [e-mail] trường hợp này ta có tất cả C54 = 5 tứ giác lồi. Đó chính là các tứ giác ABCD, ABCE, ABDE, ACDE, BCDE.

Tất cả các tứ giác này đều không chứa điểm còn lại (điểm thứ năm nằm bên ngoài tứ giác). Ta gọi các tứ giác lồi này là tứ giác lồi rỗng. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E (ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE). Và tất cả các tam giác này đều là các tam giác rỗng.

• Khả năng 2 (Hình 1.3 Bao lồi là một tứ giác chứa một điểm còn lại ở bên trong. Trong trường hợp này ta có một tứ giác lồi (kí hiệu là ABCD) chứa một điểm E ở bên trong. Tứ giác ABCD (chỉ chứa đúng một điểm E ở bên trong) được gọi là tứ giác gần rỗng. Vì không có ba điểm nào thẳng hàng nên E phải nằm về cùng phía với B (hoặc với D) của đường thẳng AC.

Do đó ta có tứ giác AECD (hoặc ABCE) là tứ giác lồi rỗng, còn tứ giác ABCE (hoặc tương ứng AECD) là tứ giác lõm. Tương tự, điểm E phải nằm cùng phía với A (hoặc với C) của đường chéo BD. Khi ấy tứ giác BEDC (hoặc tứ giác ABED) là tứ giác lồi rỗng và tứ giác ABED (hoặc tứ giác BCDE) là tứ giác lõm. Như vậy, trong Trường hợp 2 ta có hai tứ giác lồi rỗng, một tứ giác lồi gần rỗng và hai tứ giác lõm.

Ngoài ra, trong trường hợp này, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E. Đó là các tam giác: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Trong đó tất cả 6 tam giác có đỉnh E đều là tam giác rỗng (không chứa hai điểm còn lại bên trong). Vì khi kẻ đường chéo AC (hoặc BD) của tứ giác lồi ABCD thì do các điểm không thẳng hàng nên E phải nằm trong một trong hai tam giác ABC hoặc ACD (ABD hoặc BCD).

Như vậy ta có hai tam giác gần rỗng (chứa điểm E) và thêm hai tam giác rỗng nữa. • Khả năng 3 (Hình 1.4): 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Bao lồi chứa ba điểm tạo thành tam giác, thí dụ, ABC. Hai điểm còn lại E và D nằm bên trong tam giác. Do không có ba điểm nào thẳng hàng (các điểm ở vị trí tổng quát) nên hai điểm E và D xác định một đường thẳng chia mặt phẳng tam giác ABC thành hai phần sao cho có hai đỉnh của tam giác ABC, thí dụ, A và B, nằm trên cùng một nửa mặt phẳng mở.

Hai điểm E và D cùng với A và B tạo thành một tứ giác lồi rỗng ABDE. Tứ giác này là tứ giác lồi duy nhất. Bốn tứ giác ABDC, ABEC, BDCE, ADCE còn lại là các tứ giác lõm. Ngoài ra, ta có tất cả 10 tam giác được tạo thành từ năm điểm A, B, C, D, E.

Đó là các tam giác: ABC (chứa hai điểm bên trong), ACD và BEC chứa một điểm bên trong (tam giác gần rỗng). Bảy tam giác còn lại ABD, ABE, ACE, ADE, BCD, BDE, CDE là các tam giác rỗng.2 Với chín điểm cho trước ở vị trí tổng quát (không có ba điểm nào thẳng hàng) bao giờ ta cũng tìm được năm điểm tạo thành một ngũ giác lồi. Theo Erdős và Szekeres, công thức ES(5) = 9 đã được Endre Makai chứng minh.5 Tuy nhiên không có bài viết nào của E. Makai trình bày chứng minh đó, mà chỉ có phản ví dụ của E.5, xem [6]) chỉ ra rằng tồn tại tám điểm mà 8 LUAN VAN CHAT LUONG download : add [e-mail] không có năm điểm nào trong số đó tạo thành ngũ giác lồi, tức là ES(5) ≥ 9 (xem [6]).2 đã được Hoàng Chúng giới thiệu với bạn đọc Việt Nam trong Toán học và Tuổi trẻ số 4, tháng 2 năm 1967.

Ngay sau đó công thức ES(5) = 9 đã được Đoàn Hữu Dũng chứng minh trong Toán học và Tuổi trẻ số 6 tháng 6, 1967. Hoàn toàn độc lập (nhưng cùng phương pháp) với Đoàn Hữu Dũng, công thức này cũng được chứng minh bởi Bonnice năm 1974. Dưới đây chúng tôi trình bày chứng minh chi tiết công thức ES(5) = 9, kết hợp cả phương pháp hình học, (xem [1]) của Đoàn Hữu Dũng (sử dụng các đa giác lồi bao nhau) và ngôn ngữ cấu hình của Bonnice (xem [3]). Chứng minh (Đoàn Hữu Dũng, 1967; Bonnice, 1974) Lấy bao lồi của 9 điểm bất kỳ.

Gọi mỗi trường hợp (khả năng) có thể xảy ra là một cấu hình. Để phân loại các cấu hình, ta xét các đa giác lồi bao nhau, tức là đầu tiên lấy bao lồi của 9 điểm, bao lồi chỉ có thể là đa giác 9; 8; 7; 6; 5; 4; 3 đỉnh. Các điểm còn lại bên trong bao lồi tương ứng sẽ là 0; 1; 2; 3; 4; 5; 6. Khi số điểm còn lại bên trong bao lồi lớn hơn 3, ta lại lấy bao lồi của các điểm này để được các đa giác lồi.

Chỉ có duy nhất một trường hợp ba tam giác bao nhau. Các trường hợp còn lại chỉ có thể là hai hoặc một đa giác bao nhau (có thể chứa một hoặc hai điểm trong). Ta được tất cả 12 cấu hình khác nhau sau đây: Trường hợp 1 (Hình 1.6a) Cấu hình (9;0): Bao lồi là đa giác lồi 9 đỉnh. Mọi tập năm đỉnh đều tạo thành ngũ giác lồi (thậm chí lồi rỗng).

Trường hợp 2 (Hình 1.6b) Cấu hình (8;1): Bao lồi là đa giác lồi 8 đỉnh, một điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng hoặc chứa một điểm trong). Trường hợp 3 (Hình 1.6c) Cấu hình (7;2): Bao lồi là đa giác lồi 7 đỉnh, hai điểm còn lại nằm trong đa giác. Do không có ba điểm nào thẳng hàng nên năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa một hoặc hai điểm trong).

9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.6 Các cấu hình (9,0), (8,1), (7,2) Trường hợp 4 (Hình 1.7a) Cấu hình (6;3): Bao lồi là đa giác lồi 6 đỉnh, ba điểm còn lại tạo thành tam giác nằm trong bao lồi. Năm đỉnh bất kì của bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa một, hai điểm hoặc ba điểm trong). Trường hợp 5 (Hình 1.7b) Cấu hình (5;4) hoặc (5;3;1): Bao lồi là ngũ giác lồi, bốn điểm còn lại nằm trong đa giác. Ta có sẵn ngũ giác lồi chứa 4 điểm trong.

Trường hợp 6 (Hình 1.7c) Cấu hình (4;5): Bao lồi là tứ giác lồi, năm điểm còn lại tạo thành đa giác lồi. Ta có sẵn ngũ giác lồi rỗng (nằm trong tứ giác).7 Các cấu hình (6,3), (5,4), (4,5) Hình 1.8 Các cấu hình (3,6), (3,5,1) 10 LUAN VAN CHAT LUONG download : add [e-mail] Trường hợp 7 (Hình 1.8a) Cấu hình (3;6): Mọi bộ 5 trong 6 đỉnh của lục giác lồi tạo thành các ngũ giác lồi nằm trong tam giác bao lồi ngoài. Trường hợp 8 (Hình 1.8c) Cấu hình (3;5;1): Ngũ giác lồi (chứa một điểm trong và nằm trong tam giác bao lồi ngoài) đã có sẵn. Nhận xét 1 Như vậy, ta còn lại bốn cấu hình (4, 4, 1), (4, 3, 2), (3, 4, 2) và (3, 3, 3) chưa xét.9 Các cấu hình (4,4,1), (4,3,2) Hình 1.10 Các cấu hình (3,4,2), (3,3,3) Cấu hình (3, 3, 3) trở về cấu hình (3, 3, 2) nếu bỏ đi một đỉnh của tam giác trong cùng.

Cấu hình (4, 3, 2) trở về cấu hình (4, 3, 1) nếu bỏ đi một trong hai điểm trong. Cấu hình (4, 4, 1) trở về cấu hình (4, 3, 1) nếu bỏ đi một đỉnh của tứ giác trong sao cho ba đỉnh còn lại vẫn chứa một điểm trong. Vậy ta chỉ còn phải chứng minh các cấu hình (3, 3, 2), (3, 4, 2) và (4, 3, 1) chứa ngũ giác lồi.