›

Luận văn Giả thuyết Erdos - Szekeres và một số bài toán liên quan

pdf 68 trang yendo 8220
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Giả thuyết Erdos - Szekeres và một số bài toán liên quan", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_gia_thuyet_erdos_szekeres_va_mot_so_bai_toan_lien_q.pdf

Nội dung text: Luận văn Giả thuyết Erdos - Szekeres và một số bài toán liên quan

  1. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN TIẾN THỊNH GIẢ THUYẾT ERDOS¨ - SZEKERES VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN LUẬN VĂN THẠC SỸ KHOA HỌC TOÁN HỌC Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  2. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN TIẾN THỊNH GIẢ THUYẾT ERDOS¨ - SZEKERES VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN LUẬN VĂN THẠC SỸ KHOA HỌC TOÁN HỌC Chuyên ngành : Toán giải tích Mã số: 60.46.01 Người hướng dẫn khoa học: PGS.TS. Tạ Duy Phượng Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  3. Mục lục Chương 1. Giả thuyết Erdos-Szekeres¨ và một số bài toán mở rộng . . . . . . . . . . 4 1.1. Tổng quan về giả thuyết Erdos¨ – Szekeres . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1. Lịch sử của bài toán Erdos-Szekeres¨ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2. Bài toán Erdos-Szekeres¨ cho trường hợp các điểm ở vị trí bất kì . . . . . . . . . . . . . . . . . 9 1.2. Lời giải Bài toán ES(n) cho trường hợp n = 3,4,5 với tập điểm ở vị trí bất kỳ 10 1.2.1. Lời giải Bài toán ES(n) cho trường hợp n = 3 với tập điểm ở vị trí bất kỳ . . . . . . . . 14 1.2.2. Lời giải Bài toán ES(n) cho trường hợp n = 4 với tập điểm ở vị trí bất kỳ . . . . . . . . 15 1.2.3. Lời giải Bài toán ES(n) cho trường hợp n = 5 với tập điểm ở vị trí bất kỳ . . . . . . . . 17 Chương 2. Bài toán Erdos¨ về sự tồn tại đa giác lồi rỗng . . . . . . . . . . . . . . . . . . . 25 2.1. Lịch sử Bài toán Erdos¨ về đa giác lồi rỗng . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1. Đa giác lồi rỗng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.2. Đa giác lồi rỗng suy rộng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2. Lời giải bài toán H(n) cho trường hợp n = 3,4,5 với tập điểm ở vị trí bất kỳ 28 2.2.1. Chứng minh công thức H(n) cho trường hợp n = 3 với tập điểm ở vị trí bất kỳ . . . 32 2.2.2. Chứng minh công thức H(n) cho trường hợp n = 4 với tập điểm ở vị trí bất kỳ . . . 32 2.2.3. Chứng minh công thức H(n) cho trường hợp n = 5 với tập điểm ở vị trí bất kỳ . . . 35 Chương 3. Chứng minh giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1. Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 55 3.2. Chứng minh giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Kếtluận 63 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  4. MỞ ĐẦU Giả thuyết Erdos-Szekeres¨ được đề cập đến từ rất sớm (vào năm 1935), xuất phát từ bài toán của Esther Klein với phát biểu rất ngắn gọn: • Giả thuyết Erdos-Szekeres¨ : Mọi tập hợp trên mặt phẳng gồm không ít hơn 2n−2 + 1 điểm ở vị trí tổng quát (không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của đa giác lồi. • Bất chấp sự đơn giản trong phát biểu, sau ba phần tư thế kỉ, giả thuyết Erdos-Szekeres¨ mới được chứng minh cho các trường hợp n = 3, 4, 5. Gần đây (năm 2006) trường hợp n = 6 mới được chứng minh nhờ máy tính. Sau 75 năm, rất nhiều kết quả mới đã làm phong phú thêm giả thuyết Erdos-Szekeres.¨ • Luận văn Giả thuyết Erdos-Szekeres¨ và một số bài toán liên quan có mục đích trình bày chứng minh một số kết quả đã biết trong bài toán (giả thuyết) Erdos-Szekeres¨ cho hai bài toán mở rộng. Bài toán thứ nhất là mở rộng của bài toán Erdos-Szekeres¨ khi bỏ điều kiện các điểm ở vị trí tổng quát (không có ba điểm nào thẳng hàng), tức là các điểm ở vị trí bất kì. Bài toán thứ hai là bài toán Erdos¨ về sự tồn tại đa giác lồi rỗng trong tập hợp các điểm bất kì trên mặt phẳng. • Luận văn gồm ba Chương. • Chương 1: Trình bày tổng quan về giả thuyết Erdos-Szekeres.¨ Các kiến thức sử dụng trong luận văn. Chứng minh công thức ES(n) = 2n−2 + 1 với n = 3,4,5 với tập điểm ở vị trí bất kỳ trong mặt phẳng. • Chương 2: Chứng minh công thức tính H(n) với n = 3,4,5 với tập điểm ở vị trí bất kỳ trong mặt phẳng. 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  5. • Chương 3: Trình bày lại một cách tóm lược công trình của Knut Dehnhardt, Heiko Harboth và Zsolt Lángi [9] đã chứng minh cho giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng mà không sử dụng máy tính. Luận văn được hoàn thành dưới sự hướng dẫn của PGS TS Tạ Duy Phượng. Tác giả xin bày tỏ lòng kính trọng và biết ơn thầy hướng dẫn đã tận tình giúp đỡ tác giả trong suốt quá trình tập dượt nghiên cứu và viết luận văn. Tác giả xin trân trọng cảm ơn các thầy cô giáo trường Đại học sư phạm thuộc Đại học Thái Nguyên và các thầy cô giáo Viện Toán học Việt Nam đã tận tâm giảng dạy và giúp đỡ tác giả hoàn thành khóa học. Đồng thời tác giả xin chân thành cảm ơn Trường Cao đẳng Công nghiệp Nam Định, nơi tác giả đang công tác, các đồng nghiệp, gia đình và bạn bè đã động viên, giúp đỡ và tạo điều kiện về mọi mặt trong quá trình tác giả học tập. Thái Nguyên, tháng 08 năm 2011 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  6. Chương 1 Giả thuyết Erdos-Szekeres¨ và một số bài toán mở rộng Trong chương này chúng tôi phát biểu giả thuyết Erdos-Szekeres¨ cho trường hợp các điểm ở vị trí tổng quát và một mở rộng của bài toán Erdos-¨ Szekeres cho trường hợp các điểm ở vị trí bất kì, đồng thời cũng trình bày chứng minh công thức Erdos-Szekeres¨ trong trường hợp n = 3,4,5 với tập hợp điểm trên mặt phẳng ở vị trí bất kỳ. 1.1. Tổng quan về giả thuyết Erdos¨ – Szekeres 1.1.1. Lịch sử của bài toán Erdos-Szekeres¨ Năm 1933, Esther Klein đã phát biểu và chứng minh bài toán sau đây. Bài toán 1.1: Với năm điểm cho trước trong mặt phẳng ở 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 bốn điểm là đỉnh của một tứ giác lồi. Dưới đây là chứng minh của Klein. 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  7. Xét đa giác lồi lớn nhất chứa tất cả năm điểm ở vị trí tổng quát. Chỉ có ba khả năng khác nhau sau đây xảy ra: Hình 1.1: Tập năm điểm ở vị trí tổng quát luôn tồn tại 4 điểm là đỉnh của một tứ giác lồi. Trường hợp thứ nhất (xem hình1.1-loại 1): Bao lồi của năm điểm là một ngũ giác. 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 (điểm còn lại nằm ngoài tứ giác lồi đó). Vậy ta có tứ giác lồi không chứa điểm nào bên trong. Erdos¨ gọi các tứ giác này là tứ giác lồi rỗng. Trường hợp thứ hai (xem hình 1.1-loại 2): Bao lồi là tứ giác ABCD chứa một điểm E ở bên trong (tứ giác lồi ABCD chứa duy nhất một điểm E ở bên trong được gọi là tứ giác lồi gần rỗng). Kẻ đường chéo AC của tứ giác thì do ba điểm bất kì trong năm điểm đã cho không thẳng hàng nên điểm E phải thuộc tam giác ABC hoặc tam giác ACD. Trong hình 1.1-loại 2 thì điểm E nằm ở bên trong tam giác ABC (bên ngoài tam giác ACD). Khi ấy AECD là tứ giác lồi rỗng. Như vậy, trong trường hợp này ta có một tứ giác lồi rỗng AECD và một tứ giác lồi gần rỗng ABCD. Trường hợp cuối cùng (xem hình 1.1-loại 3): Bao lồi là tam giác ABC, hai điểm D và E còn lại nằm bên trong tam giác. Do không có ba 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  8. điểm nào thẳng hàng nên đường thẳng đi qua hai điểm D và E sẽ chia mặt phẳng chứa tam giác thành hai phần sao cho một nửa mặt phẳng phải chứa hai đỉnh của tam giác. Hai đỉnh này cùng với hai điểm thuộc phần trong tam giác tạo thành một tứ giác lồi rỗng. Từ quan sát trên, E. Klein đã đề nghị một bài toán tổng quát sau đây. Bài toán 1.2 : Với mỗi số tự nhiên n ≥ 3, hãy xác định số nguyên dương N(n) nhỏ nhất sao cho mọi tập có tối thiểu N(n) điểm trên mặt phẳng ở vị trí tổng quát chứa n điểm tạo thành một đa giác lồi n đỉnh. Bài toán 1.2 được phát biểu trong [15] và sau này được gọi là Bài toán Erdos-Szekeres.¨ Trong [15], Bài toán 1.2 đã được tách ra thành hai bài toán: Bài toán 1.2a : Tồn tại hay không tồn tại số N(n). Bài toán 1.2b : Nếu số N(n) tồn tại thì hãy xác định N(n) như một hàm của n, tức là tìm số điểm N(n) nhỏ nhất mà từ đó có thể chọn ra được n điểm tạo thành đa giác lồi n đỉnh. Trong [15], đã trình bày chứng minh sự tồn tại số N(n) bằng hai cách hoàn toàn khác nhau: • 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 (Szekeres và các thành viên khác trong nhóm sinh viên Budapest lúc đó không ai biết định lí Ramsey, nhưng để giải bài toán của Klein đưa ra, Szekeres đã phát hiện lại và sử dụng định lí này), từ đó ta có bất đẳng thức N(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ì N(5) ≤ 210000, quá xa so 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  9. với thực tế N(5) = 9 . • Cách thứ hai: Do Erdos¨ chứng minh nhờ kết hợp hình học với lí thuyết n−2 tổ hợp và kết quả ta được một đánh giá tốt hơn N(n) ≤ C2n−4 + 1 vào năm 1935 (xem chi tiết hơn trong [15]). Sau 63 năm Chung và Graham (xem [8]) đã chứng minh được n−2 N(n) ≤ C2n−4, ∀ n ≥ 3. Ngay sau đó Kleitman và Pachter (xem [10]) đã chứng minh được n−2 N(n) ≤ C2n−4 + 7 − 2n, ∀ n ≥ 3 Cũng trong năm đó (1998) Tóth và Valtr (xem [19]) đã chứng minh được n−2 N(n) ≤ C2n−5 + 2, ∀ n ≥ 3. Sau đó 7 năm (2005) Tóth và Valtr (xem [20]) đã chứng minh được n−2 N(n) ≤ C2n−5 + 1, ∀ n ≥ 5. Như vậy đánh giá tốt nhất hiện nay là của Tóth và Valtr, tuy nhiên với 4 n = 6 thì C7 + 1 = 36 còn cách khá xa so với chứng minh của Szekeres và Peters năm 2006 là N(6) = 17, xem [18]. Theo [11], năm (1960-1961) P. Erdos¨ and G. Szekeres đã xây dựng được trường hợp tổng quát cho tập hợp chứa 2n−2 điểm ở vị trí tổng quát (không có ba điểm bất kỳ nào thẳng hàng) không chứa n-giác lồi. Do đó cận dưới của N(n) là không thể giảm được. Như vậy ta có: n−2 n−2 2 < N(n) ≤ C2n−5 + 2 Vậy với n = 5, ta xét bài toán sau: Bài toán 1.3 : Với chín điểm cho trước ở vị trí tổng quát trong mặt phẳng (tức là 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. Bài toán này lần đầu tiên được Đoàn Hữu Dũng giải và đăng trên tạp chí Toán học và Tuổi trẻ năm 1967, xem[1]. Trên các tài liệu nước 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  10. ngoài, công thức N(5) = 9 lần đầu tiên được Kalbfleisch, Kalbfleisch và Stanton chứng minh năm 1970. Tuy nhiên, cách chứng minh trên là khá cồng kềnh, do đó công thức N(5) = 9 đã được Bonnice [7] năm 1974 và Lovász năm 1979 chứng minh theo cách đơn giản hơn. Cách chứng minh của Bonnice về cơ bản trùng với cách chứng minh của Đoàn Hữu Dũng. Như vậy, với n = 5 công thức N(5) = 9 đã được chứng minh ngắn gọn bởi Đoàn Hữu Dũng vào năm 1967 [1] và Bonnice vào năm 1974 [7]. Dựa trên các đẳng thức N(3) = 3 và N(4) = 5 Erdos¨ và Szekeres đưa ra giả thuyết sau đây: Giả thuyết Erdos-Szekeres¨ (1935): Mọi tập hợp trên mặt phẳng gồm không ít hơn 2n−2 + 1 điểm ở vị trí tổng quát (không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của n giác lồi. Bất chấp sự đơn giản trong phát biểu, sau ba phần tư thế kỉ, giả thuyết Erdos¨ - Szekeres chỉ mới được chứng minh cho các trường hợp n = 3,4,5. Trường hợp n = 6 mới được Szekeres và Peters chứng minh năm 2006 nhờ máy tính (xem [18]) và Knut Dehnhardt, Heiko Harborth, and Zsolt Lángi, V.A.Koshelev chứng minh cho một số trường hợp riêng (không dùng máy tính) năm 2009. Giả thuyết Erdos¨ - Szekeres có liên quan chặt chẽ với các lĩnh vực khác của toán-tin học (lí thuyết Ramsey, lí thuyết đồ thị, hình học tổ hợp, ). Giả thuyết Erdos¨ - Szekeres cũng được gọi là Bài toán Erdos¨ - Szekeres. 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  11. 1.1.2. Bài toán Erdos-Szekeres¨ cho trường hợp các điểm ở vị trí bất kì Trong giả thuyết Erdos-Szekeres,¨ cũng như trong nhiều bài toán khác của hình học tổ hợp, thường có một điều kiện duy nhất đặt lên tập hữu hạn các điểm. Đó là điều kiện các điểm ở vị trí tổng quát (in general position), tức là không có ba điểm nào thẳng hàng. Điều kiện này không phù hợp với thực tế và dễ bị vi phạm, nhất là khi các tập có số điểm lớn (thí dụ, số các điểm là chân các con chip gắn trên một bảng điện tử của các máy móc hiện đại, hoặc số các ngôi sao trên bản đồ thiên văn,. . . ). Các tập có số điểm lớn và giả thiết sự tồn tại các điểm thẳng hàng nhiều khi là cần thiết và có lợi. Vì vậy, trong những năm gần đây, một số tác giả (xem [6]) đã xét bài toán Erdos-Szekeres¨ cho trường hợp các điểm ở vị trí bất kì. Hiển nhiên, khi bỏ điều kiện các điểm ở vị trí tổng quát (giả thiết các điểm có thể thẳng hàng), thì không thể có đa giác lồi theo nghĩa thông thường (thí dụ, ba điểm thẳng hàng không thể tạo thành tam giác theo nghĩa thông thường). Vì vậy, việc đầu tiên là phải mở rộng khái niệm đa giác lồi. Định nghĩa 1.1.1 (Đa giác lồi suy rộng). Cho một tập Ω gồm hữu hạn điểm trên mặt phẳng (ở vị trí bất kì). Ta ký hiệu convΩ là bao lồi của tập Ω. Ta nói Ω là đa giác lồi suy rộng nếu mọi điểm của Ω đều nằm trên biên của tập convΩ. Chú ý: Nếu có bốn điểm thẳng hàng thì ta chỉ coi ba điểm liên tiếp là tam giác suy rộng, còn bốn điểm liên tiếp là tứ giác suy rộng. Định nghĩa 1.1.2 (Điểm góc, điểm cạnh). Điểm v ∈ convΩ được gọi là điểm góc của tập convΩ nếu conv(Ω\{v}) 6= convΩ. Ngược lại thì v được 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  12. gọi là điểm cạnh của Ω. Nếu convΩ là đa giác lồi suy rộng thì ta cũng vẫn gọi các điểm của Ω là đỉnh (suy rộng) của đa giác lồi suy rộng convΩ. Số đỉnh của đa giác lồi suy rộng bằng số phần tử của Ω, mặc dù số đỉnh thật sự (số điểm góc) có thể ít hơn. Đỉnh của đa giác lồi suy rộng bắt buộc phải nằm trên cạnh, (trên biên) của tập convΩ, nhưng không nhất thiết phải là điểm góc của convΩ. Ta gọi các điểm góc của convΩ là đỉnh-góc, còn các đỉnh không phải là các điểm góc của convΩ là đỉnh-cạnh. Khi tất cả các đỉnh của đa giác là đỉnh-góc thì ta nói đa giác đó là đa giác chính qui. Đa giác chính qui là đa giác theo nghĩa thông thường. Bài toán ES(n): Với số n cho trước, tồn tại hay không số ES(n) sao cho mọi tập có tối thiểu ES(n) điểm trên mặt phẳng ở vị trí bất kì đều chứa n điểm là đỉnh của một n - giác lồi suy rộng? 1.2. Lời giải Bài toán ES(n) cho trường hợp n = 3,4,5 với tập điểm ở vị trí bất kỳ Dưới đây chúng tôi trình bày lời giải Bài toán ES(n) cho các trường hợp n = 3,4,5. Để thuận tiện, ta qui ước kí hiệu ∂Ω là tập Ω\int{convΩ}. Định nghĩa 1.2.1 (Cấu hình). Cho Ω là một tập hợp n điểm trên mặt phẳng ở vị trí bất kỳ (với n ≥ 3,) ta ký hiệu |Ω| là lực lượng của tập Ω. Ta gọi tập: Ω1 = Ω\∂Ω. Ω2 = Ω\{∂Ω ∪ ∂Ω1}. Ωk = Ω\{∂Ω ∪ ∂Ω1 ∪ ∪ ∂Ωk−1,k ≥ 1}. 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  13. Khi đó nếu |∂Ω| = i0;|∂Ω1| = i1; ;|∂Ωk| = ik thì ta nói là tập Ω có cấu hình (i0,i1, ,ik). Định nghĩa 1.2.2 (Cấu hình con). Cho Ω là một tập hợp n điểm trên mặt phẳng ở vị trí bất kỳ với n ≥ 3. Ta nói cấu hình (v0,v1, ,vk) chứa cấu hình con (s0,s1, ,sk) nếu với mọi i = 0, ,k thì ta luôn có: vi ≥ si, ∀ k ≥ 0. Định nghĩa 1.2.3 (Cấu hình con chuẩn tắc). Cho Ω là một tập hợp n điểm trên mặt phẳng ở vị trí bất kỳ với n ≥ 3 và P là tập con của Ω. Giả sử tập P có cấu hình (p0, p1, , pk). Ta nói cấu hình (v0,v1, ,vk) của Ω chứa cấu hình con chuẩn tắc (p0, p1, , pk) nếu : (i), (p0, p1, , pk) là cấu hình con của (v0,v1, ,vk). (ii), ∀ j = 0, ,k −1, ta giả sử tập ∂Ω j có các đỉnh là V1,V2, ,Vq với q ≥ 3. Khi đó nếu ta bỏ đi m đỉnh bất kỳ của tập ∂Ω j (q − m ≥ 3), ta giả  sử các đỉnh còn lại là V1,V2, ,Vq−m thì ∂Pj ⊂ ∂ V1,V2, ,Vq−m . Trong đó quy ta quy ước ∂Ω0 = ∂Ω. Hiển nhiên một cấu hình con chuẩn tắc là cấu hình con, điều ngược lại nói chung không đúng. Ta xét thí dụ sau( xem hình 1.2): Hình 1.2: Cấu hình (5,3,1) chứa mọi cấu hình con chuẩn tắc (4,3,1). 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  14. Mệnh đề 1. Cho Ω là tập hợp các điểm trên mặt phẳng ở vị trí bất kỳ, |Ω| ≥ 8. Nếu Ω chứa cấu hình con chuẩn tắc (4,3,1), thì luôn có năm điểm thuộc Ω là đỉnh của ngũ giác lồi suy rộng. Chứng minh. Ta có |∂Ω| ≥ 4. Gọi V1,V2, ,Vk là các đỉnh của ∂Ω với k ≥ 4. Ta gọi B,C,D là các đỉnh của ∂Ω1 và gọi A là điểm thuộc int{convΩ1}, xem hình1.3. Các tia AB, AC,AD chia mặt phẳng thành 3 miền: Hình 1.3: Cấu hình (4,3,1) luôn chứa ngũ giác lồi suy rộng Miền (I) được giới hạn bởi các tia AB và AC. Miền (II) được giới hạn bởi các tia AC và AD. Miền (III) được giới hạn bởi các tia AD và AB. Như thế bao giờ cũng tồn tại một miền có chứa không ít hơn hai đỉnh của ∂Ω, ta giả sử là miền (I) với hai đỉnh là V1 và V1. Khi đó hai đỉnh V1 , V2 cùng với C,A,B tạo thành ngũ giác lồi suy rộng, xem hình 1.4. Mệnh đề 2. Cho Ω là tập hợp điểm trên mặt phẳng ở vị trí bất kỳ, |Ω| ≥ 8. Nếu Ω chứa cấu hình con chuẩn tắc (3,3,2) thì luôn có năm điểm thuộc Ω là đỉnh của ngũ giác lồi suy rộng. Chứng minh. Ta có |∂Ω| ≥ 3, gọi V1,V2, ,Vk là các đỉnh của ∂Ω với k ≥ 3. Ta gọi D,E,F là các đỉnh của ∂Ω1, gọi A và B là điểm thuộc 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  15. Hình 1.4: Cấu hình (4,3,1) luôn chứa ngũ giác lồi suy rộng int{convΩ1}, xem hình1.5. Các tia AD, AE,BD, BF và đoạn AB chia mặt phẳng thành 3 miền: Hình 1.5: Cấu hình (3,3,2) luôn chứa ngũ giác lồi suy rộng Miền (I) được giới hạn bởi các tia BD và BF. Miền (II) được giới hạn bởi các tia AD và AE. Miền (III) được giới hạn bởi tia AE đoạn AB và tia BF. (i), Nếu miền (III) chứa ít nhất một đỉnh của ∂Ω thì đỉnh này kết hợp với A,B,F,E lập thành ngũ giác lồi suy rộng. Xem hình 1.6. (ii), Ngược lại, một trong hai miền (I) hoặc miền (II) phải chứa không ít hơn hai đỉnh của ∂Ω ( ta giả sử là miền (I)). Do đó hai đỉnh này kết 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  16. Hình 1.6: Cấu hình (3,3,2) với một đỉnh của ∂Ω thuộc miền (III) hợp với B,D,F lập thành ngũ giác lồi suy rộng. Xem hình 1.7. Hình 1.7: Cấu hình (3,3,2) với đúng hai đỉnh của ∂Ω thuộc miền (I) 1.2.1. Lời giải Bài toán ES(n) cho trường hợp n = 3 với tập điểm ở vị trí bất kỳ Công thức ES(3) = 3: Mọi tập có tối thiểu ba điểm cho trước trên mặt phẳng ở vị trí bất kì (các điểm có thể thẳng hàng) bao giờ ta cũng tìm được ba điểm là đỉnh của một tam giác suy rộng. 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  17. Chứng minh. Khi có ba điểm (n = 3) thì chỉ có thể xảy ra một trong hai khả năng: • Khả năng thứ nhất: Ba điểm không thẳng hàng. Khi ấy ba điểm tạo thành tam giác chính qui (xem hình 1.8-loại 1) . • Khả năng thứ hai: Ba điểm thẳng hàng. Khi ấy convΩ là một đoạn thẳng nên phần trong của nó bằng rỗng và ba điểm đều nằm trên biên của tập convΩ . Do đó chúng tạo thành một tam giác suy rộng (xem hình 1.8-loại 2). Hình 1.8: Tập ba điểm luôn có tam giác lồi rỗng suy rộng Vậy ES(3) = 3. 1.2.2. Lời giải Bài toán ES(n) cho trường hợp n = 4 với tập điểm ở vị trí bất kỳ Công thức ES(4) = 5: Mọi tập có tối thiểu năm điểm cho trước trên mặt phẳng ở vị trí bất kì (các điểm có thể thẳng hàng) bao giờ ta cũng tìm được bốn điểm là đỉnh của một tứ giác lồi suy rộng. Chứng minh. Ta có tập Ω có năm điểm (năm phần tử , |Ω| = 5 ) thì chỉ có thể xảy ra một trong hai khả năng: 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  18. • Khả năng thứ nhất: |∂Ω| ≥ 4, ta gọi các đỉnh của ∂Ω là V1,V2, ,Vk với k ≥ 4 . Khi đó bốn đỉnh liên tiếp của ∂Ω lập thành một tứ giác lồi suy rộng (xem hình 1.9 và 1.10 ) . Hình 1.9: Tập năm điểm có cấu hình (5) hoặc (4,1) Hình 1.10: Tập năm điểm có cấu hình (5) hoặc (4,1) • Khả năng thứ hai: |∂Ω| = 3, ta gọi các đỉnh của ∂Ω là V1,V2,V3, các điểm thuộc int{convΩ} là A và B . Khi đó tia AB chia mặt phẳng thành hai miền. Do đó phải có một miền chứa đúng hai đỉnh của ∂Ω ( kể cả đỉnh thuộc tia AB), hai đỉnh này kết hợp với AB lập thành tứ giác lồi rỗng suy rộng ( xem hình 1.11). 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  19. Hình 1.11: Tập năm điểm có cấu hình (3,2) Mặt khác: Ta có thể chỉ ra bốn điểm không tạo thành tứ giác lồi (tạo thành tứ giác lõm, xem hình 1.12). Vậy ES(4) = 5. Hình 1.12: Tập bốn điểm không có tứ giác lồi suy rộng 1.2.3. Lời giải Bài toán ES(n) cho trường hợp n = 5 với tập điểm ở vị trí bất kỳ Công thức ES(5) = 9: Mọi tập có tối thiểu chín điểm cho trước trên mặt phẳng ở vị trí bất kì (các điểm có thể thẳng hàng) bao giờ ta cũng tìm được năm điểm là đỉnh của một ngũ giác lồi suy rộng. Ta sử dụng phương pháp xét bao lồi của tập Ω theo chiều giảm dần về số đỉnh của ∂Ω. 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  20. Chứng minh. Ta có tập Ω có chín điểm (chín phần tử , |Ω| = 9 ) thì chỉ có thể xảy ra một trong ba khả năng: Khả năng thứ 1. |∂Ω| ≥ 5, ta gọi các đỉnh của ∂Ω là V1,V2, ,Vk với k ≥ 5 . Khi đó năm đỉnh liên tiếp của ∂Ω lập thành một ngũ giác lồi suy rộng (ta không quan tâm đến các điểm thuộc int{convΩ}) xem hình 1.13. Hình 1.13: Tập có chín điểm chứa ngũ giác lồi suy rộng Khả năng thứ 2. |∂Ω| = 4, ta gọi các đỉnh của ∂Ω là V1,V2, ,V4. Khi đó ta cần xét các cấu hình sau:(4,5); (4,4,1); (4,3,2) : 1. Cấu hình (4,5): Ta có |∂Ω| = 4 và |∂Ω1| = 5. Gọi A,B,C,D,E là các đỉnh thuộc ∂Ω1. Khi ấy các điểm A,B,C,D,E là đỉnh của ngũ giác lồi suy rộng cần tìm. Xem hình 1.14 và 1.15. Hình 1.14: Tập có cấu hình (4,5) 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  21. Hình 1.15: Tập có cấu hình (4,5) 2. Cấu hình (4,4,1): Ta có |∂Ω| = 4 và |∂Ω1| = 4. Gọi B,C,D,E là các đỉnh thuộc ∂Ω1 và A là đỉnh thuộc int{convΩ1}. Ta chia tứ giác B,C,D,E thành hai tam giác bởi một đường chéo (giả sử là BD, tương ứng AC.) (i), Điểm A thuộc trong phần trong của tam giác BCD hoặc tam giác BDE. Khi đó ta có cấu hình(4,4,1) chứa cấu hình con chuẩn tắc (4,3,1). Vậy theo mệnh đề 1 Ω chứa các điểm là đỉnh của ngũ giác lồi suy rộng. Xem hình 1.16 Hình 1.16: Tập có cấu hình (4,4,1) chứa năm điểm là đỉnh của ngũ giác lồi suy rộng (ii), Điểm A nằm trên đường chéo của tứ giác BCDE (thẳng hàng với hai đỉnh của ∂Ω1 - ta giả sử là B và D). Khi đó đường thẳng 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  22. chứa B,A,D chia mặt phẳng thành hai miền và sẽ có một miền chứa ít nhất hai đỉnh của ∂Ω. Hai đỉnh này kết hợp với B,A,D lập thành ngũ giác lồi suy rộng. Xem hình 1.17. Hình 1.17: Tập có cấu hình (4,4,1) có chứa ngũ giác lồi suy rộng 3. Cấu hình (4,3,2): Ta có |∂Ω| = 4 và |∂Ω1| = 3. Gọi C,D,E là các đỉnh thuộc ∂Ω1, A và B là các đỉnh thuộc int{convΩ1}. Như vậy cấu hình (4,3,2) chứa cấu hình con chuẩn tắc (4,3,1) bằng cách bớt đi một điểm thuộc int{convΩ1}. Theo mệnh đề 1 cấu hình này cho ta ngũ giác lồi suy rộng. Xem hình 1.18. Hình 1.18: Tập có cấu hình (4,3,2) 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  23. Khả năng thứ 3. Khả năng thứ ba: |∂Ω| = 3. Gọi các đỉnh của ∂Ω là V1,V2,V3. Khi đó ta cần xét các cấu hình sau: (3,6); (3,5,1); (3,4,2) và (3,3,3) : 1. Cấu hình (3,6) và (3,5,1): Ta có |∂Ω1| ≥ 5, do đó năm đỉnh liên tiếp trên ∂Ω1 lập thành ngũ giác lồi suy rộng. Xem hình 1.19 và 1.20. Hình 1.19: Tập có cấu hình (3,6) và (3,5,1) Hình 1.20: Tập có cấu hình (3,6) và (3,5,1) 2. Cấu hình (3,4,2): Ta có |∂Ω| = 3. Gọi các đỉnh của ∂Ω là V1,V2,V3, |∂Ω1| = 4 gọi các đỉnh của ∂Ω1 là C,D,E,F, A và B là các điểm thuộc int{convΩ1}. Khi đó ta chia mặt phẳng thành bốn miền, xem hình 1.21. Miền (I) được giới hạn bởi các tia BC và BF. 21 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  24. Miền (II) được giới hạn bởi tia BC đoạn AB và tia AD. Miền (III) được giới hạn bởi các tia AD và AE. Miền (IV) được giới hạn bởi tia AE đoạn AB và tia BF. Hình 1.21: Tập có cấu hình (3,4,2) chia mặt phẳng thành bốn miền • (i), Nếu miền (II) hoặc miền (IV) có chứa một đỉnh của ∂Ω ( giả sử là miền (II)). Khi đó đỉnh này kết hợp với A,B,C,D để lập thành ngũ giác lồi suy rộng. Xem hình 1.22 Hình 1.22: Tập có cấu hình (3,4,2) mà miền (II) có chứa một đỉnh của ∂Ω • (ii), Ngược lại thì miền (I) hoặc (III) phải chứa đúng hai đỉnh của ∂Ω (giả sử là miền (III)). Khi đó hai đỉnh này kết hợp với A,D,E để lập thành ngũ giác lồi suy rộng. Xem hình 1.23 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  25. Hình 1.23: Tập có cấu hình (3,4,2) mà miền (III) có chứa đúng hai đỉnh của ∂Ω 3. Cấu hình (3,3,3) Ta có |∂Ω| = 3. Gọi các đỉnh của ∂Ω là V1,V2,V3, |∂Ω1| = 3, gọi các đỉnh của ∂Ω1 là D,E,F, các điểm thuộc int{convΩ1} là A, B và C. Khi đó ta có cấu hình (3,3,3) chứa cấu hình con chuẩn tăc (3,3,2) bằng cách bỏ đi một trong ba điểm thuộc int{convΩ1}, theo mệnh đề 2 cấu hình này cho ta ngũ giác lồi suy rộng. Mặt khác: Ta có thể chỉ ra tập tám điểm không tạo thành ngũ giác lồi, xem hình 1.24. Vậy ES(5) = 9 hay mọi tập có tối thiểu chín điểm ở vị trí bất kì trong mặt phẳng luôn có năm điểm là đỉnh của ngũ giác lồi suy rộng. Hình 1.24: Tập tám điểm không có ngũ giác lồi 23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  26. Như vậy ta đã chứng minh được các công thức ES(3) = 3, ES(4) = 5, ES(5) = 9. Vậy ta đã chứng minh được giả thuyết Erdos-Szekeres¨ cho các trường hợp n = 3,4,5 với tập điểm ở vị trí bất kỳ. Khi tập hợp điểm ở vị trí tổng quát trong mặt phẳng (không có ba điểm bất kỳ nào thẳng hàng) sẽ là một trường hợp riêng của bài toán ta đã xét. 24 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  27. Chương 2 Bài toán Erdos¨ về sự tồn tại đa giác lồi rỗng Chương này chúng tôi trình bày Bài toán Erdos¨ về sự tồn tại đa giác lồi rỗng. Đặc biệt là chứng minh bài toán H(5) =10 với tập hợp điểm trên mặt phẳng ở vị trí bất kỳ. 2.1. Lịch sử Bài toán Erdos¨ về đa giác lồi rỗng Năm 1978 Erdos¨ đã đặt một bài toán mới liên quan tới giả thuyết Erdos-Szekeres,¨ đó là Bài toán về đa giác lồi rỗng (xem [15]). Trước hết chúng ta định nghĩa đa giác lồi rỗng. 2.1.1. Đa giác lồi rỗng Định nghĩa 2.1.1 (Đa giác lồi rỗng). Cho S là tập hợp các điểm ở vị trí tổng quát trong mặt phẳng (không có ba điểm nào thẳng hàng) với |S| = k,k ≥ 3. Đa giác P căng bởi các điểm của Q trong S với số phần tử của |Q| = n,n ≤ k được gọi là đa giác lồi rỗng n đỉnh ( n-lỗ) trong S nếu nó không chứa các điểm khác của S thuộc phần trong của nó. Ở đây|S| và |Q| là kí hiệu số phần tử của tập S và Q. Kí hiệu H(n) là số nguyên dương nhỏ nhất sao cho mọi tập S các điểm ở vị trí tổng quát với |S| ≥ H(n) chứa đa giác rỗng n đỉnh. 25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  28. Bài toán Erdos¨ về đa giác lồi rỗng (1978) Cho n là một số tự nhiên bất kì, n ≥ 3. Hãy xác định số nguyên dương nhỏ nhất H(n), nếu nó tồn tại, sao cho mọi tập S có tối thiểu H(n) điểm ở vị trí tổng quát trên mặt phẳng, chứa n điểm là đỉnh của một đa giác lồi rỗng. Dễ dàng thấy rằng H(3) = 3; H(4) = 5 (xem hình 1.1.) Sử dụng cách tiếp cận hình học trực tiếp, Harborth (1978) đã chứng minh rằng H(5) = 10, tức là từ mười điểm ở vị trí tổng quát có thể chọn ra được năm điểm tạo thành ngũ giác lồi rỗng. Từ hình 2.1 cho thấy, tập chín điểm ở vị trí tổng quát không chứa năm điểm nào tạo thành ngũ giác lồi rỗng (tồn tại hai ngũ giác lồi, nhưng cả hai đều không rỗng). Hình 2.1: Tập 9 điểm ở vị trí tổng quát không tồn tại ngũ giác lồi rỗng có cấu hình (3,5,1). 26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  29. Tuy nhiên, với n ≥ 7 bất kì, Horton (1983) [12] đã xây dựng ví dụ tập với n điểm ở vị trí tổng quát không chứa 7- giác lồi rỗng nào. Do đó, H(n) = ∞ với mọi số tự nhiên n ≥ 7. Như vậy, bài toán về đa giác lồi rỗng của Erdos¨ đã có câu trả lời cho n ≤ 5 và n ≥ 7. Có rất nhiều cố gắng để chứng minh hay bác bỏ sự tồn tại của H(6). Năm 2003, bằng máy tính, Overmars [17] đã tìm ra 29 điểm ở vị trí tổng quát không chứa lục giác lồi rỗng. Như vậy, nếu H(6) tồn tại thì H(6) ≥ 30. Năm 2007 Koselev [13] đã đưa ra định lý sau đây: Định lý 2.1.2 (Koselev). Mọi tập với tối thiểu 463 điểm ở vị trí tổng quát trên mặt phẳng đều chứa sáu điểm tạo thành lục giác lồi rỗng. Vậy đánh giá tốt nhất hiện nay là 30 ≤ H(6) ≤ 463. Trong chương này chúng tôi phát biểu bài toán Erdos¨ mở rộng về sự tồn tại của đa giác lồi rỗng suy rộng, nghĩa là các điểm có thể ở vị trí bất kỳ. Do đó trước tiên ta cần mở rộng định nghĩa về đa giác lồi rỗng. 2.1.2. Đa giác lồi rỗng suy rộng Định nghĩa 2.1.3 (Đa giác lồi rỗng suy rộng ). Cho S là tập hợp các điểm ở vị trí bất kì trong mặt phẳng với |S| = k,k ≥ 3, và P là đa giác rỗng n đỉnh ( n-lỗ, với k ≥ n ≥ 3) trong convS. Nếu mọi điểm của P đều nằm trên biên của tập convP thì P được gọi là đa giác lồi rỗng suy rộng. Ta xét thí dụ sau đây: Thí dụ: Nếu tập Ω gồm năm điểm A,B,C,D,E với điểm E nằm trên cạnh AB thì convΩ là tứ giác lồi ABCD, còn conv(Ω\{A}) là tứ giác lồi BCDE nên conv(Ω\{A}) 6= convΩ, vậy A là điểm góc của tập convΩ. 27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  30. Nhưng conv(Ω\{E}) cũng chính là tứ giác lồi ABCD nên conv(Ω\{E}) = convΩ, vậy E không phải là điểm góc của tập convΩ (xem 2.2). Hình 2.2: Năm điểm tạo thành đa giác lồi rỗng suy rộng Bài toán H(n): Cho n là một số tự nhiên bất kì, n ≥ 3. Hãy xác định số nguyên dương nhỏ nhất H(n), nếu nó tồn tại, sao cho mọi tập S có tối thiểu H(n) điểm trên mặt phẳng ở vị trí bất kỳ đều chứa n điểm là đỉnh của một đa giác lồi rỗng suy rộng? 2.2. Lời giải bài toán H(n) cho trường hợp n = 3,4,5 với tập điểm ở vị trí bất kỳ Trong phần này ta sẽ chứng minh công thức H(n) của bài toán Erdos¨ về sự tồn tại của đa giác lồi rỗng suy rộng với tập điểm ở vị trí bất kỳ. Ta vẫn sẽ sử dụng phương pháp bao lồi theo chiều giảm dần về số điểm của ∂Ω-bao lồi ngoài cùng lớn nhất của tập hợp điểm, như trong Chương 1. Định nghĩa 2.2.1 (Cấu hình dạng (m,a1, ,ak) ). Cho Ω là một tập hợp n điểm trên mặt phẳng ở vị trí bất kỳ với n ≥ 3. Ta nói tập Ω có cấu hình dạng (m,a1, ,ak) nếu ai = const,∀i = 1, ,k và m ≥ 3 : k (i) ∑ ai = n − m, với m ≥ 3 và n ≥ m i=1 (ii) |∂Ω| = m; |∂Ωi| = ai, ∀i = 1,k. 28 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  31. Một cấu hình dạng (m,a1, ,ak) với m ≥ 4 chưa chắc đã chứa cấu hình con chuẩn tắc dạng (m − 1,a1, ,ak). Mệnh đề 3. Cho Ω là tập hợp các điểm trên mặt phẳng ở vị trí bất kỳ trong mặt phẳng, |Ω| ≥ 8. Nếu Ω có cấu hình dạng (m,3,1) với m ≥ 4, thì luôn có năm điểm thuộc Ω lập thành ngũ giác lồi rỗng suy rộng. Chứng minh. (i) Với m ≥ 4 và nếu Ω chứa cấu hình con chuẩn tắc (4,3,1) thì theo chứng minh mệnh đề 1 cấu hình (m,3,1) chứa ngũ giác lồi suy rộng rỗng. xem hình 1.3. (ii) Ngược lại nếu Ω không chứa cấu hình con chuẩn tắc (4,3,1) thì theo chứng minh mệnh đề 1. Ta có một miền có nhiều hơn hai đỉnh của ∂Ω, ta giả sử là miền (I) có chứa k đỉnh V1,V2, ,Vk của ∂Ω với m − 1 ≥ k ≥ 2. Khi đó ta có k + 3 giác lồi rỗng ABV1,V2, ,VkC, từ k + 3 đỉnh đó ta lấy ra năm đỉnh liên tiếp ta được ngũ giác lồi suy rộng rỗng. Xem hình 2.3. Hình 2.3: Cấu hình (m,3,1) với m ≥ 4 có ngũ giác lồi rỗng suy rộng. 29 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  32. Mệnh đề 4. Cho Ω là tập hợp các điểm trên mặt phẳng ở vị trí bất kỳ trong mặt phẳng, |Ω| ≥ 8. Nếu Ω có cấu hình dạng (m,3,2) với m ≥ 3, thì luôn có năm điểm thuộc Ω lập thành ngũ giác lồi rỗng suy rộng. Chứng minh. (i) Với m ≥ 3 nếu Ω chứa cấu hình con chuẩn tắc (3,3,2) thì theo chứng minh mệnh đề 2 cấu hình (m,3,2) chứa ngũ giác lồi suy rộng rỗng. Xem hình 1.5. (ii) Ngược lại nếu Ω không chứa cấu hình con chuẩn tắc (3,3,2) thì theo chứng minh mệnh đề 2. Khi đó ta có hoặc là miền (I) hoặc (II) có nhiều hơn hai đỉnh của ∂Ω, hoặc là miền (III) có nhiều hơn một đỉnh của ∂Ω. Ta giả sử là miền (III) có chứa k đỉnh V1,V2, ,Vk của ∂Ω với m − 1 ≥ k ≥ 1. Khi đó ta có k + 4 giác lồi rỗng ABEV1,V2, ,VkF, từ k + 4 đỉnh đó lấy ra năm đỉnh liên tiếp ta được ngũ giác lồi suy rộng rỗng. Xem hình 2.4. Hình 2.4: Cấu hình (m,3,2) với m ≥ 3 có ngũ giác lồi rỗng suy rộng. 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  33. Mệnh đề 5. Cho Ω là tập hợp các điểm trên mặt phẳng ở vị trí bất kỳ trong mặt phẳng, |Ω| ≥ 7. Nếu Ω có cấu hình dạng (m,1) với m ≥ 6, thì luôn có năm điểm thuộc Ω lập thành ngũ giác lồi rỗng suy rộng. Chứng minh. Ta gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,Vm với m ≥ 6 và gọi điểm thuộc int{convΩ} là A. Ta kẻ đường thẳng qua A và V1, đường thẳng AV1 chia mặt phẳng thành hai miền (I) và (II). Ta luôn có một miền chứa không ít hơn 3 đỉnh của ∂Ω - trừ ra đỉnh V1, ba đỉnh liên tiếp này kết hợp với A và V1 tạo thành ngũ giác lồi suy rộng rỗng. Xem hình 2.5. Hình 2.5: Cấu hình (m,1) với m ≥ 6 có ngũ giác lồi rỗng suy rộng. Mệnh đề 6. Cho Ω là tập hợp các điểm trên mặt phẳng ở vị trí bất kỳ trong mặt phẳng, |Ω| ≥ 7. Nếu Ω có cấu hình dạng (m,2) với m ≥ 5, thì luôn có năm điểm thuộc Ω lập thành ngũ giác lồi rỗng suy rộng. Chứng minh. Ta gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,Vm với m ≥ 5 và gọi các điểm thuộc int{convΩ} là A và B. Ta kẻ đường thẳng qua A và B, đường thẳng AB chia mặt phẳng thành hai miền (I) và (II). Ta luôn có một miền 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  34. chứa không ít hơn 3 đỉnh của ∂Ω. Do đó ba đỉnh liên tiếp này kết hợp với A và B tạo thành ngũ giác lồi suy rộng rỗng. Xem hình 2.6. Hình 2.6: Cấu hình (m,2) với m ≥ 5 có ngũ giác lồi rỗng suy rộng. Sau đây ta chứng minh Công thức H(n) cho từng trường hợp n = 3,4,5. 2.2.1. Chứng minh công thức H(n) cho trường hợp n = 3 với tập điểm ở vị trí bất kỳ H(3) = 3: Thật vậy với tập Ω có đúng ba điểm, ta chỉ có hai khả năng: (i) Nếu ba điểm của Ω không thẳng hàng thì hiển nhiên là H(3) =3. (ii) Nếu ba điểm của Ω thẳng hàng thì |convΩ| = 3, thì ba điểm là một tam giác lồi rỗng suy rộng. Vậy H(3) =3. Hay mọi tập có tối thiểu ba điểm ở vị trí bất kỳ trong mặt phẳng luôn tồn tại tam giác lồi rỗng suy rộng. 2.2.2. Chứng minh công thức H(n) cho trường hợp n = 4 với tập điểm ở vị trí bất kỳ H(4) = 5: Do tập Ω có năm điểm, nên ta có ba khả năng sau: 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  35. (i) Nếu |∂Ω| = 5. Gọi các đỉnh của ∂Ω là V1,V2, ,V5, như vậy bốn đỉnh liên tiếp của ∂Ω lập thành tứ giác lồi rỗng suy rộng. Xem hình 2.7. Hình 2.7: Cấu hình (5) có chứa tứ giác lồi rỗng suy rộng. (ii) Giả sử |∂Ω| = 4. Gọi các đỉnh của ∂Ω là V1,V2, ,V4 và đỉnh thuộc int{convΩ} là A. Như vậy xảy ra hai khả năng sau: 1. Khả năng thứ nhất Điểm A thuộc phần trong của tam giác V1V2V4 ( kể cả đỉnh A thuộc cạnh V2V4,) khi đó AV2V3V4 lập thành tứ giác lồi rỗng suy rộng. Xem hình 2.8. Hình 2.8: Cấu hình (4,1) luôn chứa tứ giác lồi rỗng suy rộng. 2. Khả năng thứ hai Ngược lại điểm A thuộc phần trong của tam giác V1V2V4 ( không kể đỉnh A thuộc cạnh V2V4, khi đó V1V2AV4 lập thành tứ giác lồi rỗng suy rộng. Xem hình 2.9. 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  36. Hình 2.9: Cấu hình (4,1) luôn chứa tứ giác lồi rỗng suy rộng. (iii) Giả sử |∂Ω| = 3. Gọi các đỉnh của ∂Ω là V1,V2,V3, gọi các đỉnh thuộc int{convΩ} là A và B. Ta kẻ đường thẳng AB chia mặt phẳng thành hai miền (I) và(II). Như vậy bao giờ cũng tồn tại một miền chứa không ít hơn hai đỉnh của ∂Ω ( giả sử là miền (I)). Khi đó hai đỉnh này kết hợp với A và B lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.10. Hình 2.10: Cấu hình (3,2) có chứa tứ giác lồi rỗng suy rộng. Mặt khác: Ta có thể chỉ ra tập bốn điểm không tạo thành ngũ giác lồi, xem hình 1.12. Vậy H(4) = 5. Hay mọi tập có tối thiểu năm điểm ở vị trí bất kỳ trong mặt phẳng luôn tồn tại tứ giác lồi rỗng suy rộng. 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  37. 2.2.3. Chứng minh công thức H(n) cho trường hợp n = 5 với tập điểm ở vị trí bất kỳ Ta cần chứng minh H(5) = 10 - Mọi tập gồm tối thiểu mười điểm ở vị trí bất kỳ trên mặt phẳng luôn tồn tại năm điểm lập thành ngũ giác lồi rỗng suy rộng. Ta lần lượt xét các khả năng sau (theo chiều giảm dần về số điểm của tập ∂Ω): Trường hợp 1 (|∂Ω| = 10 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V10. Hiển nhiên một xích có độ dài bằng năm tạo thành một ngũ giác lồi rỗng suy rộng. Xem hình 2.11. Hình 2.11: Tập 10 điểm có |∂Ω| = 10, chứa ngũ giác lồi rỗng suy rộng. Trường hợp 2 (|∂Ω| = 9 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V9. Gọi điểm thuộc int{convΩ} là A. Ta có được cấu hình (9,1). Theo mệnh đề 5 đường thẳng AV1 chia mặt phẳng thành hai miền (I) và (II). Ta luôn có một miền chứa không ít hơn ba đỉnh của ∂Ω, ba đỉnh liên tiếp này kết hợp với A và V1 tạo thành ngũ giác lồi rỗng suy rộng. Xem hình 2.12. 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  38. Hình 2.12: Tập 10 điểm có |∂Ω| = 9, chứa ngũ giác lồi rỗng suy rộng. Trường hợp 3 (|∂Ω| = 8 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V8. Gọi các điểm thuộc int{convΩ} là A và B. Ta có được cấu hình (8,2). Theo mệnh đề 6 đường thẳng AB chia mặt phẳng thành hai miền (I) và (II). Ta luôn có một miền chứa không ít hơn 3 đỉnh của ∂Ω, ba đỉnh liên tiếp này kết hợp với A và B tạo thành ngũ giác lồi rỗng suy rộng. Xem hình 2.13. Hình 2.13: Tập 10 điểm có |∂Ω| = 8, chứa ngũ giác lồi rỗng suy rộng. Trường hợp 4 (|∂Ω| = 7 ). Ta gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V7. Gọi các điểm thuộc int{convΩ} là A, B và C. Ta có được cấu hình (7,3). Kẻ đường thẳng qua A và B, đường thẳng AB chia mặt phẳng thành hai miền (I) và (II) và giả sử điểm C thuộc miền (I). Ta có hai khả năng sau: 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  39. • Khả năng thứ nhất: Miền (II) chứa không ít hơn ba đỉnh của ∂Ω, ba đỉnh liên tiếp này kết hợp với A và B tạo thành ngũ giác lồi suy rộng rỗng. Xem hình 2.14. Hình 2.14: Tập 10 điểm có |∂Ω| = 7, chứa ngũ giác lồi rỗng suy rộng. • Khả năng thứ hai: Ngược lại miền (I) sẽ chứa không ít hơn năm đỉnh của ∂Ω. Ta kết hợp lại các đỉnh trên miền (I) với A và B. Ta được cấu hình dạng (m,1) với m = 7. Theo mệnh đề 5 ta có được ngũ giác lồi rỗng suy rộng. Xem hình 2.15. Hình 2.15: Tập 10 điểm có |∂Ω| = 7, chứa ngũ giác lồi rỗng suy rộng. Trường hợp 5 (|∂Ω| = 6 ). Ta gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V6. Ta xét hai cấu hình sau (6,4) và (6,3,1). 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  40. 1. Cấu hình (6,4) Ta gọi các đỉnh của ∂Ω1 là A, B, C và D. Kẻ đường thẳng qua C và D, đường thẳng CD, chia mặt phẳng thành hai miền (I) và (II) và ta giả sử điểm A và B thuộc miền (I) (nếu không ta đổi tên các đỉnh A, B, C, D). Ta có hai khả năng sau: • Khả năng thứ nhất: Miền (II) chứa không ít hơn ba đỉnh của ∂Ω, ba đỉnh liên tiếp này kết hợp với C và D tạo thành ngũ giác lồi rỗng suy rộng. Xem hình 2.16. Hình 2.16: Tập 10 điểm có |∂Ω| = 6, có cấu hình (6,4). • Khả năng thứ hai: Ngược lại miền (I) sẽ chứa không ít hơn bốn đỉnh của ∂Ω. Ta kết hợp lại các đỉnh trên miền (I) với C và D. Ta được cấu hình dạng (k,2) với k ≥ 6. Theo mệnh đề 6 ta có được ngũ giác lồi rỗng suy rộng. Xem hình 2.17. Hình 2.17: Tập 10 điểm có |∂Ω| = 6, có cấu hình (6,4). 38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  41. 2. Cấu hình (6,3,1) Gọi các đỉnh của ∂Ω1 là B, C, D và đỉnh thuộc int{convΩ1} là A. Theo mệnh đề 3 cấu hình (6,3,1) có chứa ngũ giác lồi rỗng suy rộng. Xem hình 2.18. Hình 2.18: Tập 10 điểm có |∂Ω| = 6, có cấu hình (6,3,1). Trường hợp 6 (|∂Ω| = 5 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V5. Ta xét các cấu hình sau: (5,5); (5,4,1) và (5,3,2). 1. Cấu hình (5,5) Gọi các đỉnh của ∂Ω1 là A, B, C, D và E. Hiển nhiên ta có ngũ giác lồi rỗng suy rộng ABCDE. Xem hình 2.19. Hình 2.19: Tập 10 điểm có |∂Ω| = 5, có cấu hình (5,5). 2. Cấu hình (5,4,1) Gọi các đỉnh của ∂Ω1 là B, C, D , E. Gọi đỉnh thuộc int{convΩ1} là A. Khi đó ta chia mặt phẳng thành bốn miền 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  42. sau: Xem hình 2.20. Miền (I) được giới hạn bởi các tia AB và AC. Miền (II) được giới hạn bởi các tia AC và AD. Miền (III) được giới hạn bởi các tia AD và AE. Miền (IV) được giới hạn bởi các tia AE và AB. Như vậy bao giờ cũng tồn tại một miền chứa không ít hơn hai Hình 2.20: Tập 10 điểm có |∂Ω| = 5, có cấu hình (5,4,1). đỉnh của ∂Ω, ta giả sử là miền (I), các đỉnh này kết hợp cùng với A,B và C lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.21. Hình 2.21: Tập 10 điểm có |∂Ω| = 5, có cấu hình (5,4,1). 3. Cấu hình (5,3,2) Ta gọi các đỉnh của ∂Ω1 là C, D, E. Gọi các đỉnh thuộc int{convΩ1} là A và B. Theo mệnh đề 4 cấu hình này cho ta ngũ giác lồi rỗng suy rộng. 40 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  43. Trường hợp 7 (|∂Ω| = 4 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2, ,V4. Ta xét các cấu hình sau: (4,6); (4,5,1); (4,4,2) và (4,3,3). 1. Cấu hình (4,6) Gọi các đỉnh của ∂Ω1 là A, B, C, D, E và F. Hiển nhiên năm đỉnh liên tiếp cho ta ngũ giác lồi rỗng suy rộng. Xem hình 2.22. Hình 2.22: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,6). 2. Cấu hình (4,5,1) Gọi các đỉnh của ∂Ω1 là B, C, D, E, F, đỉnh thuộc int{convΩ1} là A. Ta có hai khả năng sau: • Khả năng thứ nhất. Điểm A thuộc vào phần trong của một trong các tam giác sau: BFC, FEB, EDF, DCE và CBD (ta giả sử là tam giác BFC). Khi đó điểm A ở vị trí lồi với tứ giác lồi CDEF. Vậy ACDEF tạo thành một ngũ giác lồi rỗng suy rộng. Xem hình 2.23. • Khả năng thứ hai. Ngược lại điểm A không thuộc vào phần trong của một trong các tam giác trên. Khi đó ta chia mặt phẳng thành năm miền sau ( xem hình 2.24): Miền (I) được giới hạn bởi các tia AB và AC. Miền (II) được giới hạn bởi các tia AC và AD. 41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  44. Hình 2.23: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,5,1). Miền (III) được giới hạn bởi các tia AD và AE. Miền (IV) được giới hạn bởi các tia AE và AF. Miền (V) được giới hạn bởi các tia AF và AB. Khi đó: Hình 2.24: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,5,1). [i] Tồn tại một trong năm miền chứa ít nhất hai đỉnh của ∂Ω, ta giả sử là miền (I) và giả sử hai điểm đó là V1, V2. Khi đó ABV1V2C lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.25. [ii] Ngược lại mỗi miền chứa nhiều nhất một đỉnh của ∂Ω, ta giả sử là miền (I) là miền không có đỉnh nào của ∂Ω - được tô mầu xanh, vì |∂Ω| = 4. Khi đó: 42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  45. Hình 2.25: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,5,1). [*] Nếu có một đỉnh ∂Ω nằm trong vị trí lồi với các tứ giác lồi ABCD, ACDE, ADEF và AEFB ( miền gạch chéo), thì ta thu được ngũ giác lồi rỗng suy rộng (ta giả sử là miền (II) và đỉnh đó là V1 ). Khi đó ABCV1D lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.26. Hình 2.26: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,5,1). 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  46. [ ] Ngược lại thì bốn đỉnh của ∂Ω phải thuộc vào đúng bốn miền (*), sao cho mỗi miền (*) chứa đúng một đỉnh của ∂Ω (còn một miền (*) thuộc phần trong của miền (I)). Như vậy có ba đỉnh liên tiếp nằm trong vị trí lồi với đường thẳng ED (hoặc EF). Do đó chúng cùng với ED (hoặc EF ) lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.27. Hình 2.27: Tập 10 điểm có |∂Ω| = 4, có cấu hình (4,5,1). 3. Cấu hình (4,4,2) Gọi các đỉnh của ∂Ω1 là C, D, E, F. Gọi các đỉnh thuộc int{convΩ1} là A và B. Chia mặt phẳng thành bốn miền sau (xem hình 2.28): Miền (I) được giới hạn bởi các tia AC và AD. Miền (II) được giới hạn bởi tia AD, đoạn AB và tia BE. Miền (III) được giới hạn bởi các tia BE và BF. 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  47. Miền (IV) được giới hạn bởi tia BF doạn AB và tia AC. Khi đó: Hình 2.28: Tập 10 điểm có |∂Ω| = 4 và có cấu hình (4,4,2). • Khả năng thứ nhất Miền (II) hoặc miền (IV) chứa ít nhất một đỉnh của ∂Ω, ta giả sử là miền (II) và đỉnh đó là V1. Vậy ADV1EB lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.29 Hình 2.29: Tập 10 điểm có |∂Ω| = 4 và có cấu hình (4,4,2). • Khả năng thứ hai Ngược lại miền (I) hoặc miền (III) phải có một miền chứa nhiều hơn hai đỉnh của ∂Ω, giả sử là miền (I) và hai đỉnh đó là V1 và V2. Vậy ACV1V2D lập thành ngũ giác lồi rỗng suy rộng.Xem hình 2.30. 4. Cấu hình (4,3,3) Gọi các đỉnh của ∂Ω1 là D, E, F. Gọi các đỉnh thuộc intΩ1 là A, B và C. Ta chia mặt phẳng thành ba miền sau ( xem 45 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  48. Hình 2.30: Tập 10 điểm có |∂Ω| = 4 và có cấu hình (4,4,2). hình 2.31): Miền (I) được giới hạn bởi các tia AD và AF. Miền (II) được giới hạn bởi các tia BD và BE. Miền (III) được giới hạn bởi các tia CE và CF. Như thế phải có một miền có nhiều hơn hai đỉnh của ∂Ω, ta giả sử Hình 2.31: Tập 10 điểm có |∂Ω| = 4 và có cấu hình (4,3,3). là miền (I) và hai đỉnh đó là V1và V2. Khi đó AFV1V2D lập thành ngũ giác lồi rỗng suy rộng. Xem hình 2.32. Trường hợp 8 (|∂Ω| = 3 ). Gọi các đỉnh của ∂Ω lần lượt là V1,V2,V3. Ta xét các cấu hình sau: (3,7); (3,6,1); (3,5,2); (3,4,3); (3,3,4) và (3,3,3,1). 46 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  49. Hình 2.32: Tập 10 điểm có |∂Ω| = 4 và có cấu hình (4,3,3). 1. Cấu hình (3,7) Hiển nhiên thất giác thuộc int{convΩ} sẽ cho ta ngũ giác lồi rỗng suy rộng. 2. Cấu hình (3,6,1) Cấu hình (3,6,1) chứa cấu hình con chuẩn tắc dạng (m,1) với m = 6. Theo mệnh đề 5 cấu hình này chứa ngũ giác lồi rỗng suy rộng. 3. Cấu hình (3,5,2)Cấu hình (3,5,2) chứa cấu hình con chuẩn tắc dạng (m,2) với m = 5. Theo mệnh đề 6 cấu hình này chứa ngũ giác lồi rỗng suy rộng. 4. Cấu hình (3,4,3) Ta gọi các đỉnh của ∂Ω1 là D, E, F, G. Gọi các đỉnh thuộc int{convΩ1} là A, B và C. Ta có hai khả năng sau: • Khả năng thứ nhất: Tồn tại một cạnh của tam giác ABC, mà trong nửa mặt phẳng không chứa đỉnh còn lại của tam giác có đúng ba đỉnh của ∂Ω1, (ta giả sử như hình 2.33). Khi đó ABFGD lập thành một ngũ giác lồi rỗng suy rộng. Xem hình 2.33. • Khả năng thứ hai: Ngược lại mỗi cạnh của tam giác ABC chia mặt phẳng thành hai miền và trong mỗi miền chứa đúng hai đỉnh của ∂Ω1. Khi đó ta chia mặt phẳng thành bốn miền sau. Xem 47 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  50. Hình 2.33: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,4,3). hình 2.34: Miền (I) được giới hạn bởi tia AE, đoạn AC và tia CD. Miền (II) được giới hạn bởi tia AE, đoạn AB và tia BF. Miền (III) được giới hạn bởi tia BF, đoạn BC và tia CG. Miền (IV) được giới hạn bởi các tia CD và CG. Ta có ba miền liên tiếp là (I), (II) và (III) ở trong vị trí lồi với Hình 2.34: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,4,3). các tứ giác lồi tương ứng là ACDE, ABFE và BCGF. Như vậy phải tồn tại ít nhất một đỉnh của ∂Ω thuộc vào vị trí lồi với một trong các tứ giác lồi trên (vì bao lồi ngoài cùng là một tam giác – do đó muốn bao được cầu hình (4, 3) bên trong thì các đỉnh của nó không thể nằm về một nửa mặt phẳng của đường thẳng 48 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  51. DG), ta giả sử đỉnh đó là V1 và thuộc vào miền (I). Vậy ta được ngũ giác lồi rỗng suy rộng ACDV1E. Xem hình 2.35. Hình 2.35: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,4,3). 5. Cấu hình (3,3,4) Ta gọi các đỉnh của ∂Ω1 là E, F, G. Gọi các đỉnh thuộc int{convΩ1} là A, B, C và D. Ta có hai khả năng sau: • Khả năng thứ nhất: Có ít nhất một đỉnh của ∂Ω1 nằm trong vị trí lồi với tứ giác lồi ABCD ( phần được gạch chéo). Khi đó đỉnh này kết hợp với tứ giác lồi ABCD để được ngũ giác lồi rỗng suy rộng. Xem hình 2.36. Hình 2.36: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,4). 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  52. • Khả năng thứ hai: Ngược lại phải có ba đỉnh liên tiếp E, F, G của ∂Ω1 thuộc vào ba miền (*) liên tiếp, ta giả sử như hình sau (xem hình 2.37). Gạch chéo các miền con bên ngoài tam giác lồi EFG mà nếu Hình 2.37: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,4). có một đỉnh của ∂Ω nằm trong vị trí lồi với các tứ giác lồi CBEF và CDGF. Như vậy phải tồn tại ít nhất một đỉnh của ∂Ω thuộc vào vị trí lồi với một trong các tứ giác lồi trên (vì bao lồi ngoài cùng là một tam giác – do đó muốn bao được cấu hình (3, 4) bên trong thì các đỉnh của nó không thể nằm về một nửa mặt phẳng của đường thẳng FG). Do đó ta được ngũ giác lồi rỗng suy rộng. Xem hình 2.38. 6. Cấu hình (3,3,3,1) Ta gọi các đỉnh của ∂Ω1 là E, F, G. Gọi các đỉnh của ∂Ω2 là B, C, D và đỉnh thuộc int{convΩ2} là A. Ta chia mặt phẳng thành ba miền, xem hình 2.39: Miền (I) được giới hạn bởi các tia AB và AC. Miền (II) được giới hạn bởi các tia AC và AD. Miền (III) được giới hạn bởi các tia AD và AB. Khi đó ta có hai khả năng sau: 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  53. Hình 2.38: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,4). Hình 2.39: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). • Khả năng thứ nhất. Tồn tại một miền chứa đúng hai đỉnh của ∂Ω1. Giả sử là miền (I) và hai đỉnh đó là E và F. Vậy ta được ngũ giác lồi rỗng suy rộng là ABEFC. Xem hình 2.40. • Khả năng thứ hai. Ngược lại mỗi miền (I), (II), (III) chứa đúng một đỉnh của ∂Ω1, ta giả sử đỉnh E thuộc miền (I), đỉnh F thuộc miền (II), đỉnh G thuộc miền (III). Khi đó ta chia lại mặt phẳng thành ba miền mới là (xem hình 2.41 ): Miền (IV) được giới hạn bởi các tia AB và AC. Miền (V) được giới hạn bởi các tia AC và AD. Miền (VI) được giới hạn bởi các tia AD và AB. Khi đó : [i] Tồn tại một miền trong các miền (IV), (V), (VI) chứa đúng 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  54. Hình 2.40: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). Hình 2.41: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). hai đỉnh của ∂Ω. Giả sử là miền (IV) và hai đỉnh đó là V1 và V2. Vậy ta được ngũ giác lồi rỗng suy rộng là CEV1V2F. Xem hình 2.42. [ii] Mỗi miền (IV), (V), (VI) chứa đúng một đỉnh của ∂Ω. [*] Tồn tại một đỉnh của ∂Ω nằm trong vị trí lồi với các tứ giác (miền gạch chéo): ABEC và ACFD trong miền (IV). ACFD và ADGB trong miền (V). ADGB và ABEC trong miền (VI). Thì ta thu được ngũ giác lồi rỗng suy rộng, ta giả sử là 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  55. Hình 2.42: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). đỉnh V1 nằm trong vị trí lồi của tứ giác lồi ABEC. Vậy ta có được ngũ giác lồi rỗng suy rộng ABEV1C. Xem hình 2.43. Hình 2.43: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). [ ] Ngược lại mỗi miền (*) chứa đúng một đỉnh của ∂ {convΩ}. Khi đó với hai đỉnh của ∂Ω thuộc hai miền (*) liên tiếp chúng luôn nằm trong vị trí lồi với một trong các tam giác 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  56. CEF, DFG và tam giác BEG. Vậy ta có được ngũ giác lồi rỗng suy rộng. Xem hình 2.44. Hình 2.44: Tập 10 điểm có |∂Ω| = 3 và có cấu hình (3,3,3,1). Như vậy ta đã chứng minh được các công thức: H(3) = 3, H(4) = 5, H(5) = 10. 54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  57. Chương 3 Chứng minh giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng. Trong chương này chúng tôi trình bày lại một cách tóm lược công trình của Knut Dehnhardt, Heiko Harboth và Zsolt Lángi [9] đã chứng minh cho giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng mà không sử dụng máy tính. 3.1. Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6. Trong chương 1, chúng tôi đã phát biểu Giả thuyết Erdos-Szekeres,¨ với n = 6 chúng ta cần chứng minh được rằng: Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 (1935): Mọi tập hợp trên mặt phẳng gồm không ít hơn 17 điểm ở vị trí tổng quát (không có ba điểm bất kỳ nào thẳng hàng) đều chứa 6 điểm là đỉnh của lục giác lồi. Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 đã được George Szekeres và Lindsay Peters chứng minh hoàn toàn nhờ sự trợ giúp của máy tính vào năm 2006, (xem [18]). 55 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  58. 3.2. Chứng minh giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 trong một số trường hợp riêng. Nhận xét 3.2.1. Giả sử Ω là tập 17 điểm trong mặt phẳng ở vị trí tổng quát và có cấu hình (s1,s2, ,sk); k ≥ 0 ta thấy: (i), Nếu ∀ i = 0, ,k mà |si| ≥ 6 thì Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6 được chứng minh. (ii), Như vậy chúng ta còn phải chứng minh Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6, khi tập Ω có cấu hình (s1,s2, ,sk); k ≥ 0 mà ∀ i = 0, ,k thì |si| ≤ 5. Như vậy ta có tất cả 72 loại cấu hình cho tập Ω từ (5,5,5,2), (5,5,4,3), , (3,3,3,3,3,2). (iii), Chúng tôi trình bày lại một cách tóm lược công trình của Knut Dehnhardt, Heiko Harboth và Zsolt Lángi [9] đã chứng ming Giả thuyết Erdos-Szekeres¨ với trường hợp n = 6, khi tập Ω có ∂Ω = Ω\int{convΩ} là một ngũ giác lồi. Kết quả chính của họ là định lý sau đây: Định lý 3.2.2. Nếu Ω là một tập 17 điểm trong mặt phẳng ở vị trí tổng quát (không có ba điểm bất kỳ nào thẳng hàng). Nếu ∂Ω = Ω\int{convΩ} = 5, thì Ω chứa 6 điểm là đỉnh lục giác lồi. Để chứng minh định lý 3.2.2 ta cần có các định nghĩa và một loạt các bổ đề sau: Nếu Ω = {A1 : i = 1,2, ,n} là một tập hữu hạn điểm trong mặt phẳng ở vị trí tổng quát(tức là không có ba điểm nào thẳng hàng). Ta kí hiệu V (Ω) là tập các điểm thuộc ∂Ω. 56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  59. Định nghĩa 3.2.3 (Vượt qua chính xác m-cạnh (beyond exactly m-edges)). Giả sử a,b là hai điểm phân biệt trong mặt phẳng. Ta kí hiệu: [a,b] là đoạn thẳng đóng với điểm cuối là a và b. L(a,b) là đường thẳng chứa a và b. L+ (a,b) là tia đóng đi ra từ a và chứa b. L− (a,b) là tia đóng đi ra từ a trong L(a,b) và không chứa b. Nếu tập Ω có |∂Ω| = s; s ≥ 3 là một s-giác lồi. Gọi b là một điểm thuộc Ω. Khi đó nếu điểm b không nằm trên bất kỳ đường biên nào của ∂Ω và được tách hoàn toàn từ đúng m cạnh của ∂Ω, với 1 ≤ m ≤ s, thì chúng ta nói rằng điểm b là vượt qua chính xác m-cạnh của ∂Ω. Nếu các đường biên là các đường đi qua các cạnh E1,E2, ,Em của ∂Ω với 1 ≤ m ≤ s, thì ta có thể nói rằng điểm điểm b là vượt qua chính xác m-cạnh E1,E2, ,Em của ∂Ω. Xem hình 3.1. Hình 3.1: Điểm b vượt qua chính xác 2-cạnh của P. Định nghĩa 3.2.4 (Tập hợp đồng nhất ). Nếu A và B là các tập hợp điểm trong mặt phẳng ở vị trí tổng quát. Giả sử có một song ánh f : A → B sao cho với mỗi a1,a2,a3 ∈ A, bộ ba (a1,a2,a3) và ( f (a1), f (a2), f (a3)) có sự định hướng giống nhau hoặc là có sự định hướng ngược nhau (opposite orientation), độc lập với cách chọn a1, a2 và a3. Khi đó chúng ta nói rằng 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  60. tập A và tập B là các tập hợp đồng nhất. Chúng ta thừa nhận một loạt các bổ đề sau: Bổ đề 1. Cho Ω là một tập hữu hạn điểm trong mặt phẳng ở vị trí tổng quát. Nếu ∂Ω và Q là các đa giác lồi với Q ⊂ int{convΩ}. Nếu X ⊂ ∂Ω là một tập vượt qua chính xác cạnh của Q, thì ∂Q ∪ X là các điểm ở trong vị trí lồi (in convex position). Xem hình 3.2. Hình 3.2: Nếu X thuộc miền được gạch chéo thì X ở trong vị trí lồi với Q. Bổ đề 2. Nếu {Pi : i = 1,2, ,m} là một họ của t tam giác, q tứ giác, p ngũ giác sao cho p + q + t = m và M = ∂ {P1 ∪ P2 ∪ ∪ Pm} là một m−giác (x1,x2, ,xm) sao cho [xi,xi+1] là một cạnh của Pi. Ngoài ra Pi và Pi+1 có phần trong rời nhau với mọi i = 1,2, ,m. Nếu M thuộc phần m trong của k−giác P0, và giả sử rằng nếu các điểm của W = ∪1=0 ∂Pi là ở vị trí tổng quát. Nếu q + 2t < k, thì W có chứa lục giác lồi. Xem hình 3.3. Trong các chứng minh chúng tôi thường sử dụng bổ đề 2 với k = 5. Bổ đề 3. Nếu Ω là một tập 11 điểm trên mặt phẳng ở vị trí tổng quát sao cho ∂Ω là một ngũ giác lồi, Q = ∂ {Ω\V (Ω)} là một tam giác và ∂ {Ω\V (Ω) ∪ {q}} là một tứ giác với mọi đỉnh q ∈ V (Q), thì Ω chứa lục 58 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  61. Hình 3.3: Với {Pi : i = 1,2, ,5} giác lồi. Xem hình 3.4. Hình 3.4: Các điểm r1,r2,r3 và qi luôn tạo thành một tứ giác lồi với i = 1,2,3. Bổ đề 4. Nếu Ω là một tập 13 điểm trên mặt phẳng ở vị trí tổng quát sao cho ∂Ω là một ngũ giác lồi, Q = ∂ {Ω\V (Ω)} là một tam giác, thì Ω chứa lục giác lồi. Bổ đề 5. Nếu Ω là một tập không ít hơn 13 điểm trên mặt phẳng ở vị trí tổng quát sao cho ∂Ω là một ngũ giác lồi, Q = ∂ {Ω\V (Ω)} là một tam giác, và Ω không chứa 6 đỉnh tạo thành một hình lục giác lồi, thì Q đồng nhất với một trong các loại sau: Loại 0; loại 1; loại 2; loại 3a; loại 3b; 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  62. loại 4a; loại 4b và loại 4c như trong các hình sau (Xem hình 3.5): Hình 3.5: Bổ đề 6. Nếu Ω là một tập 17 điểm trên mặt phẳng ở vị trí tổng quát sao cho ∂Ω là một ngũ giác lồi, Q = ∂ {Ω\V (Ω)} là một tứ giác, thì Ω chứa lục giác lồi. 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  63. Bổ đề 7. Nếu Ω là một tập hợp điểm trên mặt phẳng ở vị trí tổng quát sao cho ∂Ω và Q = ∂ {Ω\V (Ω)} là một ngũ giác lồi, và R = Ω\{∂Ω ∪ ∂Q} có một tập con loại 3a hoặc một tập con đồng nhất với một trong các kiểu loại 5a; loại 5b và loại 5c, thì Ω chứa lục giác lồi. Xem hình 3.6. Hình 3.6: Với các đỉnh của ∂R là r1,r2,r3,r4 và các đỉnh thuộc int{convR} là t1,t2,t3. Bổ đề 8. Nếu Ω là một tập 17 điểm trên mặt phẳng ở vị trí tổng quát có cấu hình (5,5,5,2) tức là |∂Ω| = 5; |∂Q| = 5; |∂R| = 5 và |T| = 2, thì Ω chứa lục giác lồi. Chứng minh. Định lý 3.2.2 Ta có ∂Ω = Ω\int{convΩ} = 5. Gọi Q = Ω\∂Ω thì ∂Q = Q\int{convQ}. Gọi R = Ω\{∂Ω ∪ ∂Q} thì ∂R = R\int{convR}. Gọi T = Ω\{∂Ω ∪ ∂Q ∪ ∂R}. Khi đó ta xét các khả năng sau: 1. Nếu |∂Q| = 3 thì theo bổ đề 4 ta có Ω chứa lục giác lồi. 2. Nếu |∂Q| = 4 thì theo bổ đề 6 ta có Ω chứa lục giác lồi. 3. Nếu |∂Q| = 5 thì ta lại xét các trường hợp sau theo |∂R|. 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  64. • (i) Nếu |∂R| = 3 thì theo bổ đề 5 ta có: ∂R∪T là loại 4a, 4b hoặc 4c. Do đó nó chứa một tập con loại 3a. Theo bổ đề 3 ta có Ω chứa lục giác lồi. • (ii) Nếu |∂R| = 4 thì ta có: ∂R ∪ T chứa một tập con đồng nhất với loại 5a; loại 5b hoặc loại 5c. Theo bổ đề 7 ta có Ω chứa lục giác lồi. • (iii) Nếu |∂R| = 5 thì ta có cấu hình (5,5,5,2) tức là |∂Ω| = 5; |∂Q| = 5; |∂R| = 5 và |T| = 2. Theo bổ đề 8 ta có Ω có chứa lục giác lồi. Như vậy định lý được chứng minh. Trong [9] đã chứng minh được 24 trên tổng số 72 lớp cấu hình được phân loại bởi Bonnice[7]. Như vậy bài toán vẫn còn lại 48 lớp cấu hình chưa có lời giải, cho nên đây vẫn còn là một bài toán mở, mà hy vọng sẽ sớm có lời giải đáp. 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  65. KẾT LUẬN Luận văn trình bày tổng quan về giả thuyết Erdos-Szekeres¨ và chứng minh giả thuyết cho các trường hợp n = 3,4,5 với tập hợp điểm ở vị trí bất kỳ. Đặc biệt là chứng minh công thức H(5) =10 với tập hợp điểm trên mặt phẳng ở vị trí bất kỳ (mặc dù vào năm 1978 Harboth đã chứng minh công thức H(5) =10 với tập hợp điểm trên mặt phẳng ở vị trí tổng quát, xong do hạn chế về ngôn ngữ và khả năng nên chúng tôi không có được bài báo này- Harboth h., Konvece Funfecke in ebenen Punktmegen, Elem. Math. 33 (1978), 116-118, MR 80a:52003). Đồng thời luận văn trình bày tóm lược lại công trình của Knut Dehn- hardt, Heiko Harboth và Zsolt Lángi, đã chứng minh cho giả thuyết Erdos-¨ Szekeres với trường hợp n = 6 trong một số trường hợp riêng mà không sử dụng máy tính. Với khuôn khổ, thời gian và năng lực của chúng tôi còn nhiều hạn chế, cho nên còn rất nhiều câu hỏi mở chưa tìm được câu trả lời. Hy vọng với sự lỗ lực của các nhà toán học trong thời gian gần nhất sẽ trả lời được phần nào các câu hỏi mở nêu trên. 63 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  66. Tài liệu tham khảo [1] Đoàn Hữu Dũng, Lời giải của bài toán Ecđôtsơ trong một trường hợp đặc biệt, Tạp chí Toán học và Tuỏi trẻ, số 33, tháng 6, 1967, trang 14-16. [2] Đoàn Hữu Dũng, Tạ Duy Phượng, Nguyễn Tiến Thịnh, Về bài toán Erdos-Szekeres¨ cho ngũ giác lồi suy rộng, Kỉ yếu Hội Thảo khoa học các chuyên toán bồi dưỡng học sinh giỏi bậc THPT, Nguyễn Văn Mậu chủ biên, Nam Định, 26-28, 2010, trang 140-153. [3] Đoàn Hữu Dũng, Nguyễn Tiến Thịnh, Về sự tồn tại ngũ giác gần rỗng trong số chín điểm ở vị trí bất kỳ, Kỉ yếu Hội Thảo khoa học các chuyên đề Olympic toán học khu vực cấp THPT, Nguyễn Văn Mậu chủ biên, Phú Thọ, 09-10/04, 2011, trang75-82. [4] Đoàn Hữu Dũng, Nguyễn Tiến Thịnh, Bài toán Erdos-Szekeres¨ cho ngũ giác lồi suy rộng, Tạp chí Toán học và Tuổi trẻ, số 41, tháng 8 năm 2011, trang 12-14. [5] Hoàng Đức Tân, Định lí Ramsey, Tạp chí Toán học và Tuổi trẻ, số 178, tháng 2 năm 1991, trang 1-2. [6] Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmovic,´ Ferran Hurtado, Scott D. Kominers, Stefan Langer- man, Attila Pór, and R. David, Every large point set contains many collinear points or an empty pentagon, arXiv:0904.0262v2 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  67. [math.CO] 24 Apr 2009, 1-16 hoặc Graphs and Combinatorics 27(1): 47-60 (2011) [7] W. E. Bonnice, On convex polygons determined by a finite planar set, Amer. Math. Monthly 81 (1974), 749-752. MR 50:8301. [8] F. R. L. Chung, R.L. Graham, Forced convex n-gons in the place, Discrete Comput.Geom. 19 :367-371, 1998.MR 99e:52020. [9] Knut Dehnhardt, Heiko Harborth and Zsolt Lansgi, A partial proof of the Erdos-Szekeres¨ conjecture for hexagons, Journal of Pure and Applied Mathematics: Advances and Applications; Volume no: 2, Issue no: 1, August (2009), 69-86 [10] D. Kleitman, L. Pachter, Finding convex sets among points in the place, Discrete Comput.Geom. 19 :405-410, 1998.MR 99e:52021. [11] P. Erdos¨ and G. Szekeres, On some extremum problems in elemen- tary geometry, Ann. Universitatis Scientiarum Budapestinensis, Sec- tio Mathematica III-IV (1960-1961), 53-62. [12] Joseph D. Horton, Sets with empty convex 7-gons, Canadian Math. Bulletin 26 (4):482–484, 1983. MR 85f:52007 [13] V. A. Koshelev, On the Erdos-Szekeres¨ Problem, Doklady Mathemat- ics, 2007, Vol. 76, No1, pp. 603-605. [14] V. A. Koshelev, On Erdos-Szekeres¨ problem for empty hexagons in the plane, Modeling and analysis of information systems, Vol. 16, 2, 22-74, 2009, On Russian. [15] Wanter D. Morris and Valeru Soltan, The Erdos-Szekeres¨ problem on points in convex position - A survey,Bulletin of the American Math- ematical Society (N. S.), 37(4):437–458, 2000. 65 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
  68. [16] Jessca L. Nielsen, On the of Empty Convex Hexagons, Harvey Mudd College, 2003. [17] M. Overmars, Finding sets of points without empty convex 6- gons, Discrete and Computational Geometry 29(1):153–158, 2003. doi:10.1007/s00454-002-2829-x . [18] George Szekeres and Lindsay Peters, Computer solution to the 17-point Erdos-Szekeres¨ problem,The ANZIAM Journal 48: 151–164. doi:10.1017/S144618110000300X, . [19] Géza Tóth, Paven Valtr, Note on thr Erdos-Szekeres¨ therem, Discrete Comput.Geom. 19 :457-459, 1998.MR 99e:52022. [20] Géza Tóth, Paven Valtr, The Erdos-Szekeres¨ theorem: upper bounds and related result, Combinatorial and Computational geometry. MSRI Publication 52 :557-568, 2005. [21] P. Valtr, On empty hexagons, In Survey on discrete and computa- tional geometry, Vol. 453 of Contemporary Mathematics, pp. 433- 441, Amer. Math. Soc., 2008. 66 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên