ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN GIANG THÀNH VỀ LỤC GIÁC LỒI RỖNG LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 01 13 Người hướng dẫn khoa học PGS TS TẠ DUY PHƯỢNG H NI- 2013 Mc lc M u ă VỀ ĐA GIÁC LỒI RỖNG TỔNG QUAN VỀ BÀI TOÁN ERDOS 1.1 Bài toán 1.1.1 Bài toán 1a 1.1.2 Bài toán 1b 1.1.3 Bài toán 1.1 1.1.4 Bài toán 1.2 1.1.5 Bài toán 1.3 1.2 Bài toán 1.3 Bài toán (Bài toán tồn đa giác chứa k điểm ) 1.4 Bài toán CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) 2.1 Định lý E(6) ≤ ES(9) 2.2 Lược đồ chứng minh 2.2.1 Kí hiệu 2.2.2 Các định nghĩa 2.3 Các trường hợp đơn giản 2.4 Các trường hợp (3, ≥ 0) (≥ 6, 3) 2.4.1 Các trường hợp (3, ≥ 0) (8,3) 2.4.2 Các trường hợp (6,3) (7,3) 2.5 Các trường hợp (4, ≥ 0) (≥ 7, 4) 2.5.1 Bước 1a 2.5.2 Bước 1b 2.5.3 Bước 2.5.4 Bước 2.5.5 Tổng kết 2.6 Các trường hợp (5, 0) (≥ 7, 5, 0) 2.6.1 Các trường hợp (5, 0) (8, 5, 0) 2.6.2 Trường hợp (7, 5, 0) 2.7 Các trường hợp riêng 2.7.1 Trường hợp (5,1) 2.7.2 Trường hợp (6,1) 2.7.3 Các trường hợp (6,2) (7,1) 2.8 Các trường hợp (5, ≥ 2) VÀ HỆ QUẢ 5 5 14 16 19 21 23 23 23 25 25 27 27 27 29 34 34 35 38 38 38 40 40 40 41 41 42 43 43 2.8.1 Một quan sát 2.8.2 Các trường hợp (5, ≥ 2) 2.9 Các trường hợp (6, ≥ 4) 2.9.1 TW X ∩ TXY = ∅ 2.9.2 TW X ∩ TXY = ∅ 2.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1) 2.10.1 Quy tắc 2.10.2 Quy tắc 2.10.3 Ứng dụng Quy tắc 2.10.4 Quy tắc 2.10.5 Ứng dụng Quy tắc 1-3 2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1) 2.10.7 Trường hợp (1, 1, 1, 1, 1, 1, 1, 0) 2.10.8 Trường hợp (1, 1, 1, 1, 1, 1, 1, 1) Kết luận Tài liệu tham khảo 43 46 48 49 51 52 53 54 54 56 58 59 59 61 65 66 Mở đầu Năm 1935, Erdo˝s Szekeres đưa giả thuyết sau (giả thuyết Erdo˝sSzekeres): Mọi tập không 2n−2 + điểm mặt phẳng vị trí tổng qt (khơng có ba điểm thẳng hàng) chứa n điểm đỉnh đa giác lồi Giả thuyết Erdo˝s-Szekeres có ý nghĩa triết học sâu sắc: Từ tập hợp hỗn độn, khơng có trật tự, đủ lớn (tập điểm mặt phẳng), ta tìm tập có cấu trúc đẹp (đa giác lồi) Kí hiệu ES(n) số điểm vị trí tổng quát nhỏ mà từ ta chọn ˝s-Szekeres nói ES (n) = n điểm đỉnh n-giác lồi Khi ấy, giả thuyết Erdo 2n−2 + Bất chấp cố gắng hàng trăm nhà toán học viết hàng trăm báo, giả thuyết Erdo˝s-Szekeres chứng minh cho trường hợp n = 3, 4, 5, Trường hợp n = chứng minh gần (2006) Szekeres Peters nhờ máy tính Trên đường chứng minh giả thuyết Erdo˝s-Szekeres, nhiều phương pháp toán xuất Năm 1978 [xem 5], Erdo˝s phát biểu tốn mới, Bài tốn Erdo˝s đa giác lồi rỗng: Cho n số tự nhiên Tồn hay khơng số ngun dương nhỏ E(n) cho từ tập chứa tối thiểu E(n) điểm vị trí tổng quát mặt phẳng, chọn n điểm đỉnh đa giác lồi rỗng (đa giác không chứa điểm tập cho bên nó) Bài tốn thu hút nhiều nhà nghiên cứu hình học tổ hợp giới Năm 1978, Harborth chứng minh E(5) = 10 Năm 1983, với n, Horton xây dựng tập (sau gọi tập Horton), mà từ khơng thể lấy đa giác lồi rỗng bảy đỉnh Như vậy, phải nghiên cứu với trường hợp n = Năm 2003, Overmars chứng minh, E(6) tồn E(6) ≥ 30 Năm 2008, Gerken chứng minh E(6) ≤ ES(9) từ suy ES(6) tồn ta có đánh giá 30 ≤ E(6) ≤ 1717 Nhiều người tin rằng, E(6) = 30 Tuy nhiên, giả thuyết chưa chứng minh Luận văn Về lục giác lồi rỗng có mục đích trình bày tổng quan tốn Erdo˝s3 Szekeres tốn Erdo˝s đồng thời trình bày chứng minh chi tiết báo Gerken đánh giá E(6) ≤ ES(9) Luận văn gồm hai Chương: Chương trình bày tổng quan giả thuyết Erdo˝s-Szekeres Chương trình bày cách chứng minh E(6) ≤ ES(9) Gerken (năm 2008) Luận văn hoàn thành trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội hướng dẫn PGS TS Tạ Duy Phượng- Viện Tốn học Tơi xin bày tỏ lòng biết ơn sâu sắc tới Thầy hướng dẫn Tôi xin cảm ơn Khoa sau đại học, Thày Cô trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Viện Tốn học nhiệt tình truyền thụ kiến thức tạo điều kiện giúp đỡ tơi hồn thành khóa Cao học Và cuối cùng, xin cảm ơn Gia đình động viên khích lệ tơi nhiều thời gian nghiên cứu học tập Chương TNG QUAN V BI TON ă V A GIC LỒI RỖNG ERDOS 1.1 Bài toán Với số tự nhiên n ≥ , xác định số nguyên dương nhỏ ES(n) cho tập tạo thành từ tối thiểu ES(n) điểm mặt phẳng vị trí tổng quát phải chứa n điểm đỉnh đa giác lồi Bài toán phát biểu vào năm 1935 sau gọi Bi toỏn ErdăosSzekeres Erdăos ó gi bi toỏn ny l tốn có kết hạnh phúc (happy end problem hay happy ending problem), khơng lâu sau báo c in (1935), Gyăorgy Szekeres v Esther Klein ó tổ chức đám cưới (1937) sống hạnh phúc bên 60 năm Bài toán tách thành hai toán: 1.1.1 Bài toán 1a Tồn hay khơng tồn số ES(n)? 1.1.2 Bài tốn 1b Nếu số ES(n) tồn xác định ES(n) hàm n Sự tồn số ES(n) chứng minh hai cách Cách thứ Szekeres chứng minh không lâu sau E Klein phát biểu tốn, dựa định lí Ramsey (mà Ơng tự tìm lại khơng biết định lí này) Từ ta có bất đẳng thức ES(n) ≤ R4 (n, 5) , R4 (n, 5) số Ramsey Tuy nhiên, đánh giá lớn so với thực tế Thí dụ, với n = ES(5) ≤ 210000 xa so với ES(5) = Cỏch th hai Erdăos chng minh da trờn số quan sát hình học kết 2n−4 ta đánh giá tốt ES(n) ≤ Cn−2 + Như vậy, toán 1a trả lời khẳng định Rõ ràng ba điểm không thẳng hàng đủ để tạo tam giác nên ES(3) = Dưới ta xét số trường hợp cụ thể toán với n = 4, 5, 1.1.3 Bài toán 1.1 (E Klein) Từ năm điểm mặt phẳng vị trí tổng quát chọn bốn điểm đỉnh tứ giác lồi Đây kết cho toán trường hợp n = Bài toán E.Klein chứng minh vào năm 1932 Chứng minh Trước tiên ta nhận thấy, tồn bốn điểm khơng tạo thành tứ giác lồi (Hình 1.1) Hình 1.1 Vậy số điểm mà từ tạo thành tứ giác lồi phải khơng Xét bao lồi năm điểm (tập lồi nhỏ chứa năm điểm cho) vị trí tổng quát Chỉ có ba khả khác sau • Khả (Hình 1.2): Hình 1.2 Bao lồi năm điểm ngũ giác ABCDE Khi bốn điểm từ năm điểm tạo thành tứ giác lồi (và điểm lại nằm ngồi tứ giác lồi đó) Trong trường hợp ta có tất C54 = tứ giác lồi Đó tứ giác ABCD, ABCE, ABDE, ACDE, BCDE Tất tứ giác khơng chứa điểm lại (điểm thứ năm nằm bên tứ giác) Ta gọi tứ giác lồi tứ giác lồi rỗng Ngồi ra, ta có tất 10 tam giá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 tam giác tam giác rỗng • Khả (Hình 1.3): Hình 1.3 Bao lồi tứ giác chứa điểm lại bên Trong trường hợp ta có tứ giác lồi (kí hiệu ABCD) chứa điểm E bên Tứ giác ABCD (chỉ chứa điểm E bên trong) gọi tứ giác gần rỗng Vì khơng có ba điểm thẳng hàng nên E phải nằm phía với B (hoặc với D) đường thẳng AC Do ta có tứ giác AECD (hoặc ABCE) tứ giác lồi rỗng, tứ giác ABCE (hoặc tương ứng AECD) tứ giác lõm Tương tự, điểm E phải nằm phía với A (hoặc với C) đường chéo BD Khi tứ giác BEDC (hoặc tứ giác ABED) tứ giác lồi rỗng tứ giác ABED (hoặc tứ giác BCDE) tứ giác lõm Như vậy, Trường hợp ta có hai tứ giác lồi rỗng, tứ giác lồi gần rỗng hai tứ giác lõm Ngồi ra, trường hợp này, ta có tất 10 tam giác tạo thành từ năm điểm A, B, C, D, E Đó tam giác: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE Trong tất tam giác có đỉnh E tam giác rỗng (không chứa hai điểm lại bên trong) Vì kẻ đường chéo AC (hoặc BD) tứ giác lồi ABCD điểm không thẳng hàng nên E phải nằm trong hai tam giác ABC ACD (ABD BCD) Như ta có hai tam giác gần rỗng (chứa điểm E) thêm hai tam giác rỗng • Khả (Hình 1.4): Hình 1.4 Bao lồi chứa ba điểm tạo thành tam giác, thí dụ, ABC Hai điểm lại E D nằm bên tam giác Do khơng có ba điểm thẳng hàng (các điểm vị trí tổng quát) nên hai điểm E D xác định đường thẳng chia mặt phẳng tam giác ABC thành hai phần cho có hai đỉnh tam giác ABC, thí dụ, A B, nằm nửa mặt phẳng mở Hai điểm E D với A B tạo thành tứ giác lồi rỗng ABDE Tứ giác tứ giác lồi Bốn tứ giác ABDC, ABEC, BDCE, ADCE lại tứ giác lõm Ngồi ra, ta có tất 10 tam giác tạo thành từ năm điểm A, B, C, D, E Đó tam giác: ABC (chứa hai điểm bên trong), ACD BEC chứa điểm bên (tam giác gần rỗng) Bảy tam giác lại ABD, ABE, ACE, ADE, BCD, BDE, CDE tam giác rỗng 1.1.4 Bài tốn 1.2 Với chín điểm cho trước vị trí tổng qt (khơng có ba điểm thẳng hàng) ta tìm năm điểm tạo thành ngũ giác lồi Theo Erdo˝s Szekeres, công thức ES(5) = Endre Makai chứng minh Hình 1.5 Tuy nhiên khơng có viết E Makai trình bày chứng minh đó, mà có phản ví dụ E Makai (Hình 1.5, xem [6]) tồn tám điểm mà năm điểm số tạo thành ngũ giác lồi, tức ES(5) ≥ (xem [6]) Bài tốn 1.2 Hồng Chúng giới thiệu với bạn đọc Việt Nam Toán học Tuổi trẻ số 4, tháng năm 1967 Ngay sau cơng thức ES(5) = Đoàn Hữu Dũng chứng minh Toán học Tuổi trẻ số tháng 6, 1967 Hoàn toàn độc lập (nhưng phương pháp) với Đồn Hữu Dũng, cơng thức chứng minh Bonnice năm 1974 Dưới 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 phương pháp hình học, (xem [1]) Đồn Hữu Dũng (sử dụng đa giác lồi bao nhau) ngơn ngữ cấu hình Bonnice (xem [3]) Chứng minh (Đoàn Hữu Dũng, 1967; Bonnice, 1974) Lấy bao lồi điểm Gọi trường hợp (khả năng) xảy cấu hình Để phân loại cấu hình, ta xét đa giác lồi bao nhau, tức lấy bao lồi điểm, bao lồi đa giác 9; 8; 7; 6; 5; 4; đỉnh Các điểm lại bên bao lồi tương ứng 0; 1; 2; 3; 4; 5; Khi số điểm lại bên bao lồi lớn 3, ta lại lấy bao lồi điểm để đa giác lồi Chỉ có trường hợp ba tam giác bao Các trường hợp lại hai đa giác bao (có thể chứa hai điểm trong) Ta tất 12 cấu hình khác sau đây: Trường hợp (Hình 1.6a) Cấu hình (9;0): Bao lồi đa giác lồi đỉnh Mọi tập năm đỉnh tạo thành ngũ giác lồi (thậm chí lồi rỗng) Trường hợp (Hình 1.6b) Cấu hình (8;1): Bao lồi đa giác lồi đỉnh, điểm lại nằm đa giác Do khơng có ba điểm thẳng hàng nên năm đỉnh bao lồi tạo thành ngũ giác lồi (có thể rỗng chứa điểm trong) Trường hợp (Hình 1.6c) Cấu hình (7;2): Bao lồi đa giác lồi đỉnh, hai điểm lại nằm đa giác Do khơng có ba điểm thẳng hàng nên năm đỉnh bao lồi tạo thành ngũ giác lồi (có thể rỗng, chứa hai điểm trong) tam giác thay P P phù hợp cần) Xét tất khả phân bố đỉnh (được tổng kết Bảng 3) Ta muốn chia diện tích bên ngồi đa giác lồi i cạnh conv(I) thành miền trường hợp, nhiều tám đỉnh 8-giác lồi nằm hợp miền mà không taọ lục giác lồi rỗng Ba quy tắc đơn giản sau đủ để chứng minh điều này: 2.10.1 Quy tắc Quy tắc giải trường hợp hai đỉnh conv(I) nằm miền Hình 2.26 Quy tắc Quy tắc Gọi A1 , A2 hai đỉnh liên tiếp conv(I) nằm miền (aP b), a b hai đỉnh liên tiếp conv(J) Khi khơng đỉnh 9-giác lồi nằm miền (A1 abA2 ) mà không tạo lục giác lồi rỗng Chứng minh Từ tồn ngũ giác lồi rỗng A1 aP bA2 , P ∈ J∩ aP b chọn cách thích hợp (Hình 26).Suy ra, có điểm Q đỉnh 9-giác lồi H nằm miền ngũ giác (A1 aP bA2 ) QA1 aP bA2 lục giác lồi rỗng 53 2.10.2 Quy tắc Hình 2.27 Quy tắc Quy tắc cho ta đánh giá cận số đỉnh 9-giác lồi nằm hai miền không rỗng Quy tắc Gọi A1 , A2 hai đỉnh liên tiếp conv(I) nằm miền phân biệt (a1 P b1 ) (a2 P b2 ), a1 , b1 a2 , b2 đỉnh liên tiếp conv(J) Giả sử a1 , b1 , a2 , b2 thuộc xích lồi gồm đỉnh liên tiếp conv(J) Đặt S := (A1 b1 a2 A2 ) A1 b1 a2 A2 tứ giác lồi S := (A1 b1 A2 ) ∪ (A1 a2 A2 ) trường hợp tứ giác A1 b1 a2 A2 khơng lồi Khi đó, có nhiều hai đỉnh 9-giác lồi nằm S Chú ý Trong Quy tắc 2, b1 = a2 Chứng minh Một miền tam giác không chứa điểm J phủ kín miền S dựng cách chọn A1 , A2 điểm thích hợp ar từ đỉnh liên tiếp conv(J) nằm b1 a2 (tính b1 a2 ) Vì miền ln "chứa" miền S (theo cách xây dựng) nên suy miền S chứa tối đa hai đỉnh 9-giác lồi mà không tạo lục giác lồi rỗng (Hình 27) 2.10.3 Ứng dụng Quy tắc Hai quy tắc đủ để bố Π(2, 2, 2, 1, 0), (7, 6, ≥ 1) với Π(2, 2, 2, 1, 0, 0, 0), (7, 8, ≥ 1) với bố Π(2, 2, 2, 2, 0), (8, 6, ≥ 1) với giải trường hợp (7, 5, ≥ 1) với phân phân bố Π(2, 2, 2, 1, 0, 0), (7, 7, ≥ 1) với phân bố phân bố Π(2, 2, 2, 1, 0, 0, 0, 0), (8, 5, ≥ 1) với phân phân bố Π(2, 2, 2, 2, 0, 0), (8, 7, ≥ 1) với phân bố 54 Π(2, 2, 2, 2, 0, 0, 0), (8, 8, ≥ 1) với phân bố Π(2, 2, 2, 2, 0, 0, 0, 0) Để rõ hơn, áp dụng Quy tắc vào hai đỉnh conv(I) nằm miền Lưu ý hai đỉnh ứng với số "2" cách phân bố Với đỉnh liên tiếp conv(I) nằm miền phân biệt, áp dụng Quy tắc Lưu ý trường hợp này, Quy tắc cần áp dụng xác lần ln có vị trí khác khơng cách phân bố Điều dẫn tới tối đa 4.2=8 đỉnh 9-giác lồi H xếp vào mà không tạo lục giác lồi rỗng Một ví dụ Hình 28 Hình 2.28 Áp dụng Quy tắc cho trường hợp (7, 6, ≥ 1) với phân bố (2, 0, 2, 1, 0, 2) 55 Hình 2.29 Quy tắc 2.10.4 Quy tắc Quy tắc giải trường hợp với dãy miền mà miền chứa nhiều đỉnh conv(I), xem Hình 29 Hình 2.30 Chứng minh Quy tắc với n = Quy tắc Cho ≤ n ≤ i − Xét dãy A0 , A1 , , An+1 đỉnh liên tiếp conv(I) Với ≤ l ≤ n + 1, lấy Al ∈ (al P bl ), al bl đỉnh liên tiếp 56 conv(J) Giả sử với ≤ l ≤ n, miền (al P bl ) chứa đỉnh conv(I) a1 , b1 , a2 , b2 , , an+1 , bn+1 đỉnh liên tiếp xích lồi trích từ conv(J) Khi đó, nhiều n + đỉnh 9-giác lồi nằm hợp miền ∪n+1 l=1 (Al−1 al Al ) Chú ý Trong Quy tắc 3, bl = al+1 (1 ≤ l ≤ n) bn+1 = a1 Hơn nữa, A0 A1 nằm miền (an+1 P bn+1 ) Chứng minh Ta chứng minh quy nạp theo n Nếu n = 1, ta lập luận A1 nằm bên đường a1 b1 A0 A2 nằm bên a1 b1 ("nằm bên dưới" nghĩa nằm nửa mặt phẳng bờ a1 b1 chứa P ) Vì ngược lại, |Ta1 b1 | = dựng 9-giác lồi H nằm 9-giác lồi H cho (trường hợp t = Quan sát Mục 8) Giả sử A0 nằm bên a1 b1 (trường hợp A1 A2 nằm bên a1 b1 tương tự) Dựng miền tứ giác (A0 a1 b1 A1 ) với miền tam giác (A1 a2 A2 ) Nếu cần, thay a2 điểm thích hợp a2 ∈ A1 a2 A2 đẻ tạo miền tam giác (A1 a2 A2 ) mà khơng có điểm J nằm A1 a2 A2 Các miền phủ diện tích (A0 a1 A1 ) ∪ (A1 a2 A2 ) Với điểm nằm (A1 a2 A2 ) điều rõ ràng (A1 a2 A2 ) phủ phần diện tích Lưu ý rằng, khơng thể có điểm Q ∈ ((A0 a1 A1 ) \ (A1 a2 A2 )) \ (A0 a1 b1 A1 ) Điểm phải nằm phần diện tích bị bơi đen Hình 30 Nếu a2 nằm bên phải b1 A1 (hoặc a2 = b1 ) Q ∈ (A1 a2 A2 ) ta chọn a2 := b1 Các miền tứ giác tam giác cho phép nhiều 1+2=3 đỉnh 9-giác lồi nằm mà không tạo lục giác lồi rỗng Bước quy nạp tiếp theo, giả sử yêu cầu toán cho 1, 2, , n − Qua giả thiết quy nạp, ta thấy có nhiều (n − 1) + đỉnh 9-giác lồi nằm hợp miền ∪nl=1 (Al−1 al Al ) Nhiều hai đỉnh 9-giác lồi H nằm miền (An an An+1 )\ ∪nl=1 (Al−1 al Al ) mà không tạo lục giác lồi rỗng Do đó, số đỉnh 9-giác lồi nằm hợp miền ∪n+1 l=1 (Al−1 al Al ) nhiều (n − + 2) + = n + mà không tạo lục giác lồi rỗng Cũng từ giả thiết quy nạp, có nhiều (n − 1) + đỉnh 9-giác lồi H nằm hợp miền ∪n+1 l=2 (Al−1 al Al ) mà không tạo lục giác lồi rỗng Tương tự, nhiều hai đỉnh 9-giác lồi nằm miền (A0 a1 A1 )\∪n+1 l=2 (Al−1 al Al ) mà không tạo lục giác lồi rỗng Do đó, cận xác có hai đỉnh 9-giác lồi nằm miền (A0 a1 A1 ) (An an+1 An+1 ) Ta suy A0 phải nằm phía đường a1 b1 An+1 phải nằm phía đường an bn khơng miền (A0 a1 A1 ) (An an+1 An+1 ) thay 57 miền (A0 a1 b1 A1 ) (An an bn An+1 ) Miền chứa đỉnh 9-giác lồi mà không tạo lục giác lồi rỗng hợp của miền phủ phần diện tích tương tự Điều dẫn tới ∪nl=1 Tal bl = n < n + dựng 9-giác lồi H nằm 9-giác lồi H cho theo Quan sát Để thấy được, lưu ý a1 , b1 , a2 , b2 , , an , bn đỉnh liên tiếp xích lồi trích từ conv(J) với độ dài L > n + Từ ta có điều phải chứng minh 2.10.5 Ứng dụng Quy tắc 1-3 Dựa ba Quy tắc ta giải tất trường hợp lại (≥ 7, ≥ 5, ≥ 1) ngoại trừ (7, 7, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1), (7, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 0), (8, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 1) (Những trường hợp không cho phép áp dụng trực tiếp Quy tắc Ta giải trường hợp riêng mục sau) Với trường hợp lại, số xuất phân bố Ta lập luận sau: Với hai đỉnh liên tiếp conv(I) nằm miền, áp dụng Quy tắc Lưu ý hai điểm tương ứng với số phân bố Không có đỉnh 9-giác lồi nằm miền Bây ta chọn dãy miền liên tiếp lớn chứa tối đa đỉnh conv(I) miền áp dụng Quy tắc (tương ứng chọn Quy tắc khơng có miền miền chứa đỉnh) Số đỉnh 9-giác lồi nằm hợp miền tương ứng q + s.2, q tổng số số xuất phân bố s số chuỗi phân biệt Nhận xét rằng, s số khoảng trống hai lần xuất số phân bố Số số số phân bố, suy q + s.2 tổng phần tử dãy phân bố Dễ dàng kiểm tra đươc tổng nhỏ Do đó, trường hợp dựng lục giác lồi rỗng (ví dụ minh họa Hình 31) 58 Hình 2.31 Trường hợp (8, 8, ≥ 1) với phân bố (2, 1, 1, 1, 0, 2, 0, 1) 2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1) Trường hợp giải cách áp dụng Quy tắc với n = bảy lần với đỉnh conv(I) điểm xuất phát Mỗi miền (Ar−1 ar Ar ) bị loại lần Do vậy, hợp tất miền có nhiều (7.(5+2))/69 đỉnh 9-giác lồi nằm hợp tất miền Do đó, đòi hỏi cách tiếp cận khác cho trường hợp đặt Kí hiệu đỉnh conv(J) theo chiều kim đồng hồ thứ tự ar (1 ≤ r ≤ 8) Xét bốn đỉnh liên tiếp 8-giác lồi conv(J) as , at , au , av Lưu ý khơng có điểm conv(I) nằm phía đường as at phía đường au av ("phía dưới" hiểu nằm nửa mặt phẳng chứa P ) ngược lại ta sử dụng điểm để dựng 9-giác lồi H nằm 9-giác lồi H cho Kí hiệu Rt miền nằm phía hai đường as at at au , xem Hình 33 Hợp tất miền Rr (1 ≤ r ≤ 8) xác định miền cho đỉnh conv(I) Kí hiệu đỉnh conv(I) Am (Am ∈ (am P am+1 )), ≤ r ≤ 8, a9 := a1 ) Lưu ý Am nằm Rm Rm+1 (hoặc hai) (1 ≤ r ≤ 8, R9 := R1 ) Xét ba khả sau: Hình 2.33 Trường hợp (8, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 1) :Xác định Rt TH1: Tồn miền Rw mà khơng có Am nằm Có nhiều miền ngược lại ta dựng 9-giác lồi H nằm 9-giác lồi H cho Để rõ điều này, loại bỏ tiếp khả Rz tính chất Rw+1 , Rw+2 , Rw+3 Rw+4 Trong 61 trường hợp dầu tiên, ta có |Taw aw+1 | < ba trường hợp lại ta thay ba đỉnh 8-giác lồi a1 a2 a8 hai bốn điểm Am để dựng 9-giác lồi H nằm 9-giác lồi H cho Gọi a1 điểm liên kết với miền không chứa điểm Am Vì tồn miền độc lập với cách chọn điểm P nằm ngũ giác a6 a2 a3 a4 a5 Điểm P chắn tồn khơng dựng lục giác lồi rỗng, xem Hình 34 (một cách chọn điểm P khác giải cách phân bố khác Với trường hợp ta chọn điểm P trên) Kết quả, có nhiều ba đỉnh 9-giác lồi nằm miền (A6 a6 P a2 A1 ) khơng dựng 9-giác lồi H nằm 9-giác lồi H cho (vì 5+4=9) Ta cần chứng minh Am ∈ Rm ∩ Rm+1 với ≤ m ≤ 7, có nghĩa Am nằm bên hai đường am−1 am am+1 am+2 (2 ≤ m ≤ 7, a9 := a1 ) Để rõ hơn, ta đường a1 a2 tiến hành theo chiều kim đồng hồ để chứng minh Am nằm l−1 am−1 am ( ≤ m ≤ 7) Lưu ý đến cấu hình, n=1 Tan an+1 < l(2 ≤ l ≤ 8) suy dựng 9-giác lồi H nằm 9-giác lồi H cho theo Quan sát Mục Bây đường a1 a8 tiến hành theo chiều kim đồng hồ để chứng minh Am nằm bên đường am+1 am+2 (2 ≤ m ≤ 7, a9 := a1 ) Cuối cùng, ta giả sử khơng có Ar nằm R1 , kéo theo A1 ∈ R2 A8 ∈ R8 Do đó, trường hợp giải minh hoa hình 34 62 Hình 2.34 Trường hợp (8, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 1): R1 khơng chứa Am TH2: Ít Am nằm miền Rr (1 ≤ r ≤ 8) đặt A1 ∈ R1 \R2 Ta phải chứng minh điều dẫn đến Au ∈ Ru (3 ≤ u ≤ 8) ngược lại xuất 9-giác lồi H nằm 9-giác lồi H cho Để rõ hơn, ta xét điểm A8 , A8 ∈ R1 \ R8 9-giác lồi H := A1 a2 a3 a8 A8 nằm 9-giác lồi H cho xuất Do đó, A8 ∈ R8 Tiếp theo xét đến A7 , A6 tiếp tục Cuối cùng, ta giả giả thiết có điểm Am nằm miền Rr (1 ≤ r ≤ 8), kéo theo A2 ∈ R2 , xem hình 35 Trong trường hợp này, miền bên ngồi conv(I) chia thành miền tứ giác (Al al al+1 Al+1 ) (1 ≤ l ≤ 8, a9 := a1 , A9 := A1 ) hợp miền chứa tối đa tám đỉnh 9-giác lồi mà không tạo lục giác lồi rỗng 63 TH3: Mỗi Am nằm Rm Rm+1 Một lần nữa, miền bên ngồi conv(I) chia thành tám miền tứ giác (Al al al+1 Al+1 ) (1 ≤ l ≤ 8, a9 := a1 , A9 := A1 ) hợp miền chứa tối đa tám đỉnh 9-giác lồi mà khơng tạo lục giác lồi rỗng Hình 2.35 Trường hợp (8, 8, ≥ 1) với phân bố (1, 1, 1, 1, 1, 1, 1, 1): A1 ∈ R1 \ R2 64 Kết luận Chương Luận văn trình bày tổng quan tốn Erdo˝s-Szekeres đa giác lồi toán Erdo˝s đa giác lồi rỗng Chương Luận văn trình bày chứng minh toán Erdo˝s cho lục giác lồi rỗng, dựa theo chứng minh báo Gerken Từ đây, hệ quả, ta suy ra: Số điểm cần thiết vị trí tổng quát mà từ tìm sáu điểm đỉnh tạo thành lục giác lồi rỗng phải thỏa mãn bất đẳng thức 30 ≤ E(6) ≤ 1717 Gần đây, sử dụng cách chứng minh tương tự Gerken, Koselev chứng minh bất đẳng thức tốt 30 ≤ E(6) ≤ 463 Chứng minh Gerken Koselev tỉ mỉ, cơng phu sử dụng để nghiên cứu giả thuyết Erdo˝s toán lục giác lồi rỗng 65 Tài liệu tham khảo [1] Đồn Hữu Dũng, Lời giải tốn Ecđôtsơ trường hợp đặc biệt (với lời nhận xét Hồng Chúng), Tạp chí Tốn học 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, Bài toán Erdo˝s đa giác lồi (Bản thảo), 150 trang [3] Bonnice W E., On convex polygons determined by a finite planar set, Amer Math Monthly 81 (1974), 749-752 [4] Knut Dehnhardt, Heiko Harborth, and Zsolt Lángi, A partial proof of the Erdo˝s-Szekeres conjecture for hexagons, Journal of Pure and Applied Mathematics: Advances and Applications,Volume Number (2009), 69-86 [5] Paul Erdo˝s, Some more problems on elementary geometry, Austral Math Soc Gaz (1978), 52-54 [6] P Erdo˝s and G Szekeres, A combinatorial problem in geometry, CompositioMath 2, 463 (1935) [7] T Gerken, On empty convex hexagons in planar point set, Discrete Comput Geom., 39 (2008), 239-272 [8] H Harborth, Konvexe Funfecke in ebenen Punktmengen, Elem Math., 33 (1978), 116-118 [9] J D Horton, Sets with no empty 7-gons, Canad Math Bull., 26 (1983), 482484 [10] Kalbfleisch J.D., Kalbfleisch J.G., Stanton R.G., A combinatorial problem on convex regions, Proc Louisiana Conf Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La, 1970 Congr Numer (1970), 180-188 [11] V A Koshelev, On Erdo˝s-Szekeres problem for empty hexagons in the plane, Modeling and analysis of information systems, 16 (2009), 22-74 On Russian 66 [12] Wanter D Morris and Valeru Soltan, The Erdo˝s-Szekeres problem on points in convex position - A survey, Bulletin of the American Mathematical Society (N S.), 37(4):437–458, 2000 [13] M Overmars, Finding sets of points without empty convex 6-gons, Discrete Comput Geom., 29 (2003), 153-158 [14] M Overmars, B Scholten, I Vincent, Sets without empty convex 6-gons, Bull European Assoc Theor Comput Sci., 37 (1989), 160-168 [15] G Szekeres, L Peters, Computer solution to the 17-point Erdos-Szekeres problem, ANZIAM J., 48 (2006), 151-164 67 ... chéo BD Khi tứ giác BEDC (hoặc tứ giác ABED) tứ giác lồi rỗng tứ giác ABED (hoặc tứ giác BCDE) tứ giác lõm Như vậy, Trường hợp ta có hai tứ giác lồi rỗng, tứ giác lồi gần rỗng hai tứ giác lõm Ngoài... Trên thực tế Gerken chứng minh 9 -giác lồi (đa giác lồi đỉnh) chứa lục giác lồi rỗng Đây đánh giá tốt theo nghĩa tồn tập có bao lồi 8 giác không chứa lục giác rỗng (Overmas, 2003) Valtr (2006)... gian thay điểm thành tập lồi thể lồi; nghiên cứu sâu cấu trúc hình học tập điểm (đa giác lồi rỗng, đa giác lồi gần rỗng, đa giác lồi chứa k điểm, ); quan hệ số đa giác lồi k đỉnh tập hợp n điểm