vấn đề kết thúc có hậu

Article

May 22, 2022

Trong toán học, bài toán kết thúc có hậu là mệnh đề sau: Erdos Pal đặt tên này cho cuộc hôn nhân của Sekeresi Gyorgi và Klein Esther, người đã chứng minh định lý. Đây là một trong những kết quả ban đầu dẫn đến sự phát triển của lý thuyết Ramsey. Định lý kết thúc có hậu có thể được chứng minh bằng một phân tích trường hợp đơn giản. Nếu 4 điểm trở lên là đỉnh của thân lồi, hãy chọn 4 điểm trong số này. Ngược lại, nếu hình lồi có dạng tam giác với hai điểm nằm trong thì ta có thể chọn một trong hai điểm trong và cạnh của tam giác. Xem Peterson (2000) để biết giải thích về chứng minh này. Để có một cuộc điều tra chi tiết hơn về vấn đề, hãy xem Morris & Soltan (2000). Giả thuyết Erdos-Sekeresi là mệnh đề sau đây thể hiện chính xác mối quan hệ tổng quát hơn giữa số điểm trong tập hợp các điểm vị trí chung và đa giác lồi lớn nhất. chỉ ở vị trí bình thường 2 N - 2 + Một {\ displaystyle 2 ^ {n-2} +1} Tập hợp các con chó là lồi N {\ displaystyle n} Bao gồm các hình vuông. Giả thuyết Erdos-Sekeresi vẫn chưa được chứng minh, nhưng các ranh giới ít chính xác hơn đã được biết đến.

Đa giác lớn hơn

Năm 1935, Erdossi và Sekeresi đã chứng minh mệnh đề tổng quát sau: Chứng minh xuất hiện trong cùng một bài báo chứng minh định lý Erdos-Sekeresi cho các dãy con đơn điệu của dãy số. Gọi f (N) là tập hợp các điểm M có vị trí tổng quát trên mặt phẳng là lồi N {\ displaystyle N} Để nó là M nhỏ nhất mà phải chứa đa giác. Về vấn đề này, những điều sau được biết đến: f (3) 3. Điều này là hiển nhiên. f (4) 5. f (5) 9. Hình vẽ bên gồm 8 điểm không chứa ngũ giác lồi, chứng tỏ f (5)> 8. Phần khó của chứng minh là chứng minh rằng tập hợp tất cả chín điểm ở một vị trí tổng quát chứa các đỉnh của một ngũ giác lồi. f (6) 17. Giá trị của f (N) là chưa biết với mọi N> 6. Theo kết quả của Erdős & Szekeres (1935), f (N) là hữu hạn với mọi số nguyên dương N. Dựa trên các giá trị đã biết của f (N) cho N 3, 4 và 5, Erdos và Szekeres ban đầu Bài báo suy đoán rằng: tất cả N ≥ 3 {\ displaystyle N \ geq 3} Về f ( N ) Một + 2 N - 2 {\ displaystyle f (N) 1 + 2 ^ {N-2}} là. Sau đó, chúng tạo thành một ví dụ rõ ràng, f ( N ) ≥ Một + 2 N - 2 {\ displaystyle f (N) \ geq 1 + 2 ^ {N-2}} đã chứng minh rằng giới hạn trên được biết đến nhiều nhất khi N ≥ 7 là f ( N ) ≤ 2 N + o ( N ) {\ textstyle f (N) \ leq 2 ^ {N + o (N)}} là.

Đa giác lồi rỗng

Người ta có thể đặt câu hỏi liệu có "rỗng" tứ giác lồi, ngũ giác, v.v., trong đó tập hợp các điểm đủ lớn ở một vị trí tổng quát không chứa bất kỳ điểm nào khác trong tập hợp đó hay không. Giải pháp ban đầu cho bài toán kết thúc có hậu được áp dụng để chỉ ra rằng năm điểm ở vị trí bình thường của chúng có một tứ giác lồi rỗng như hình bên.