Bài toán mở, Tổ hợp và Toán rời rạc, Hình học, nêu năm 1935

Bài toán kết thúc có hậu (Erdős–Szekeres)

Còn mởErdős

Với mọi số nguyên $n \ge 3$ , liệu mọi tập gồm $2^{n-2} + 1$ điểm trong mặt phẳng Euclid $\mathbb{R}^2$ ở vị trí tổng quát (không có ba điểm nào thẳng hàng) có luôn chứa $n$ điểm tạo thành các đỉnh của một đa giác lồi $n$ cạnh — tức số điểm tối thiểu đảm bảo điều đó là $\mathrm{ES}(n) = 2^{n-2} + 1$ — hay không?

Người nêu, 1935Paul Erdős

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, công thức chính xác $\mathrm{ES}(n) = 2^{n-2} + 1$ mới chỉ được chứng minh cho $n = 3, 4, 5, 6$ , với $\mathrm{ES}(3) = 3$ , $\mathrm{ES}(4) = 5$ , $\mathrm{ES}(5) = 9$ và $\mathrm{ES}(6) = 17$ ; ngay cả trường hợp $n = 7$ (được phỏng đoán là $\mathrm{ES}(7) = 33$ ) vẫn còn mở. Về mặt tiệm cận, tiếp nối đột phá năm 2016 của Andrew Suk $\mathrm{ES}(n) = 2^{n + o(n)}$ , Holmsen, Mojarrad, Pach và Tardos (2020) đã cải thiện số hạng dư cận trên thành $\mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ , chỉ còn để lại một thừa số dưới hàm mũ giữa cận dưới và cận trên.

Kết quả tốt nhất đã biết

Các giá trị chính xác: $\mathrm{ES}(3) = 3$ , $\mathrm{ES}(4) = 5$ (Klein, 1933), $\mathrm{ES}(5) = 9$ (Makai–Turán, 1935) và $\mathrm{ES}(6) = 17$ (Szekeres–Peters, 2006).
Với mọi $n \ge 3$ , $2^{n-2} + 1 \le \mathrm{ES}(n) \le 2^{n + O(\sqrt{n \log n})}$ (Erdős–Szekeres 1960; Suk 2016/2017; Holmsen–Mojarrad–Pach–Tardos 2020).

Công cụ và chỗ dừng

Công cụ	Đạt được	Chỗ dừng
Phân rã cốc-nắp tỷ phần dương (Pór–Valtr, Suk)	Sử dụng định lý tỷ phần dương Pór–Valtr để phân hoạch phần lớn tập điểm thành $k$ tập con độc lập lồi nằm trong các hình nón hẹp, cho phép quy nạp đồng thời trên các dây cung lồi và lõm để hạ cơ số từ $4$ xuống $2$ .	Việc trích ra một tỷ phần dương ở mỗi tầng đệ quy làm hao hụt một hệ số $O(k^4)$ qua mỗi bước, tích lũy thành phần dư $2^{O(\sqrt{n \log n})}$ phía trên $2^{n-2} + 1$ .

Câu hỏi còn mở

Liệu mọi tập gồm $33$ điểm ở vị trí tổng quát trên mặt phẳng có luôn chứa các đỉnh của một thất giác lồi ( $\mathrm{ES}(7) = 33$ ) hay không?
Đẳng thức $\mathrm{ES}(n) = 2^{n-2} + 1$ có đúng với mọi số nguyên $n \ge 3$ hay không?

Tài liệu tham khảo

Paul Erdős, George Szekeres (1935). A combinatorial problem in geometry
George Szekeres, Lindsay Peters (2006). Computer solution to the 17-point Erdős-Szekeres problem · DOI:10.1017/S144618110000300X
Andrew Suk (2017). On the Erdős-Szekeres convex polygon problem · DOI:10.1090/jams/869 · arXiv:1604.08657