Chương 1 Giả thuyết Erdös-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 Erdös-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 Erdös- 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 Erdös-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ỳ. Tổng quan về giả thuyết Erdös – Szekeres 1. Lịch sử của bài toán Erdös-Szekeres Năm 1933, Esther Klein đã phát biểu và chứng minh bài toán sau đây.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 http://www.vn 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. Erdös 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.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 http://www.vn đ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.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.2 được phát biểu trong [15] và sau này được gọi là Bài toán Erdös-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).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 http://www.vn với thực tế N(5) = 9.
• Cách thứ hai: Do Erdös 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. Như vậy đánh giá tốt nhất hiện nay là của Tóth và Valtr, tuy nhiên với n = 6 thì C74 + 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].
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 2n−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 http://www.vn 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 Erdös và Szekeres đưa ra giả thuyết sau đây: Giả thuyết Erdös-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 Erdös - 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.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 Erdös - 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 Erdös - Szekeres cũng được gọi là Bài toán Erdös - Szekeres. 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www. Bài toán Erdös-Szekeres cho trường hợp các điểm ở vị trí bất kì Trong giả thuyết Erdös-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 Erdös-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. 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. Đ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 http://www.vn 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. 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Ω} .