Bài toán lớn

Thế kỷ 20

1. 1935
   Bài toán kết thúc có hậu (Erdős–Szekeres)Tổ hợp và Toán rời rạc, Hình học. Cần bao nhiêu điểm ở vị trí tổng quát trên mặt phẳng để chắc chắn có một đa giác lồi $n$ đỉnh? Được Esther Klein nêu ra với $n = 4$ vào năm 1933 — dẫn đến đám cưới của bà với George Szekeres và tên gọi "Bài toán kết thúc có hậu" do Paul Erdős đặt — giá trị chính xác được phỏng đoán $\mathrm{ES}(n) = 2^{n-2} + 1$ mới chỉ được chứng minh cho $n \le 6$, dù Andrew Suk đã chứng minh tiệm cận $\mathrm{ES}(n) = 2^{n + o(n)}$ vào năm 2016.ErdősCòn mở
2. 1941
   Giả thuyết Erdős–Turán về cơ sở cộng tínhSố học và Lý thuyết số, Tổ hợp và Toán rời rạc. Nếu một tập số tự nhiên cuối cùng phủ hết mọi số nguyên qua tổng từng đôi (một cơ sở tiệm cận bậc $2$), liệu có phải luôn tồn tại những số nguyên có số cách biểu diễn tùy ý lớn thành tổng của hai phần tử? Được Paul Erdős và Pál Turán nêu năm 1941, giả thuyết $\limsup_{n \to \infty} r_A(n) = \infty$ đến nay vẫn còn mở.ErdősCòn mở
3. 1946
   Bài toán khoảng cách đơn vị của ErdősHình học, Tổ hợp và Toán rời rạc. Có tối đa bao nhiêu cặp trong $n$ điểm trên mặt phẳng cách nhau một khoảng bằng $1$? Bị chặn trên bởi $O(n^{4/3})$, trong khi một cấu trúc lý thuyết số năm 2026 đã bác bỏ giả thuyết $n^{1+o(1)}$ của Erdős bằng cách chứng minh $u(n) = \Omega(n^{1+c})$.ErdősCòn mở
4. 1948
   Giả thuyết Erdős–StrausSố học và Lý thuyết số. Được Paul Erdős và Ernst G. Straus phát biểu năm 1948, giả thuyết phân số Ai Cập này hỏi liệu $4/n$ có luôn viết được thành tổng nghịch đảo của ba số nguyên dương hay không. Vì mọi phân tích cho ước $d \mid n$ đều nhân tỷ lệ thành phân tích cho $n$, chỉ cần chứng minh bài toán khi $n = p$ là số nguyên tố. Các hằng đẳng thức đại số đơn giản giải quyết ngay các số nguyên tố $p \not\equiv 1 \pmod{24}$, và các hệ phủ môđun lớn hơn loại trừ hầu hết các lớp thặng dư, cho phép máy tính kiểm tra tới $n = 10^{17}$, nhưng một hệ phủ hoàn chỉnh gồm hữu hạn hằng đẳng thức là không thể tồn tại.ErdősCòn mở
5. 1960
   Giả thuyết hoa hướng dương Erdős–RadoTổ hợp và Toán rời rạc. Một họ gồm các tập có tối đa $w$ phần tử có thể lớn tới mức nào nếu không chứa $r$ tập có giao từng đôi hoàn toàn trùng nhau? Được Paul Erdős và Richard Rado nêu năm 1960 cùng cận giai thừa $w! (r - 1)^w$, bài toán đã có bước đột phá lịch sử năm 2019 nhờ Alweiss, Lovett, Wu và Zhang (sau được làm sắc thành $(C r \log w)^w$), nhưng cận hàm mũ thuần túy $C_r^w$ vẫn còn mở.ErdősCòn mở
6. 1973
   Giả thuyết Erdős về cấp số cộngSố học và Lý thuyết số, Tổ hợp và Toán rời rạc. Nếu tổng các nghịch đảo $\sum_{n \in A} \frac{1}{n} = \infty$, liệu tập $A$ có buộc phải chứa các cấp số cộng dài tùy ý? Đã được chứng minh cho $k = 3$ bởi Thomas Bloom và Olof Sisask (2020), còn mọi độ dài $k \ge 4$ vẫn đang mở.ErdősCòn mở
7. 1977
   Giả thuyết Erdős–HajnalTổ hợp và Toán rời rạc. Trong khi một đồ thị $n$ đỉnh tổng quát chỉ đảm bảo chứa clique hoặc tập độc lập cỡ logarit $\Theta(\log n)$, Paul Erdős và András Hajnal phỏng đoán năm 1977 rằng việc cấm một đồ thị con cảm sinh cố định $H$ bất kỳ sẽ buộc phải có clique hoặc tập độc lập cỡ đa thức $n^{\delta_H}$.ErdősCòn mở