Bài toán mở, Tổ hợp và Toán rời rạc, nêu năm 1977

Giả thuyết Erdős–Hajnal

Còn mởErdős

Với mọi đồ thị hữu hạn $H$ , tồn tại hằng số $\delta_H > 0$ sao cho mọi đồ thị $G$ có $n$ đỉnh không chứa $H$ làm đồ thị con cảm sinh đều có một clique hoặc một tập độc lập với kích thước đa thức ít nhất là $n^{\delta_H}$ .

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

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

Tính đến năm 2026, giả thuyết Erdős–Hajnal vẫn còn mở đối với các đồ thị bị cấm tổng quát $H$ có từ $6$ đỉnh trở lên (như $P_6$ và $C_6$ ). Với $H$ bất kỳ, cận dưới phổ quát tốt nhất hiện biết cho tập thuần nhất lớn nhất trong một đồ thị $n$ đỉnh không chứa $H$ là $2^{c_H \sqrt{\log n \log\log n}}$ (Bucić, Nguyen, Scott và Seymour, 2023). Về mặt cấu trúc, chuỗi công trình Induced subgraph density của Nguyen, Scott và Seymour đã giải quyết giả thuyết cho đồ thị không chứa $P_5$ — hoàn tất mọi đồ thị có tối đa $5$ đỉnh — đồng thời chứng minh rằng các lớp đồ thị di truyền có chiều VC bị chặn đều thỏa mãn tính chất Erdős–Hajnal đa thức.

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

Với mọi đồ thị $H$ , mọi đồ thị $n$ đỉnh không chứa $H$ cảm sinh đều có một clique hoặc tập độc lập với kích thước ít nhất $2^{c_H \sqrt{\log n \log\log n}}$ (Bucić, Nguyen, Scott và Seymour, 2023).
Toàn bộ giả thuyết đa thức đúng cho mọi đồ thị $H$ có $|V(H)| \le 5$ (khép lại với $C_5$ bởi Chudnovsky–Scott–Seymour–Spirkl 2021 và $P_5$ bởi Nguyen–Scott–Seymour 2023) cùng mọi đồ thị thu được từ chúng qua phép thế đỉnh.

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

Công cụ	Đạt được	Chỗ dừng
Định lý Rödl và phương pháp tăng mật độ lặp / phân rã phong tỏa	Sử dụng định lý Rödl (rằng đồ thị không chứa $H$ luôn có tập con $\varepsilon$ -hạn chế cỡ tuyến tính) kết hợp với các cấu trúc phong tỏa cân bằng để chứng minh cận $2^{c_H \sqrt{\log n \log\log n}}$ và giải quyết trường hợp $P_5$ cùng chiều VC bị chặn.	Với $H$ tổng quát mà bao đóng có thể có chiều VC không bị chặn, các bước tăng mật độ làm co tập đỉnh theo hệ số tựa đa thức qua nhiều tầng trừ khi duy trì được phép tách cấu trúc ở thang đa thức.

Câu hỏi còn mở

Giả thuyết Erdős–Hajnal có đúng cho các đồ thị không chứa $P_6$ và các đồ thị không chứa $C_6$ hay không?
Liệu cận dưới tổng quát cho $H$ bất kỳ có thể được nâng từ $2^{c_H \sqrt{\log n \log\log n}}$ lên $2^{c_H (\log n)^\alpha}$ với một số mũ $\alpha > 1/2$ nào đó hay không?

Tài liệu tham khảo

Paul Erdős, András Hajnal (1989). Ramsey-type theorems · DOI:10.1016/0166-218X(89)90045-0
Maria Chudnovsky (2014). The Erdős–Hajnal conjecture—a survey · DOI:10.1002/jgt.21730
Matija Bucić, Tung Nguyen, Alex Scott, Paul Seymour (2024). Induced subgraph density. I. A loglog step towards Erdős–Hajnal · DOI:10.1093/imrn/rnae066 · arXiv:2301.10147
Tung Nguyen, Alex Scott, Paul Seymour (2023). Induced subgraph density. VII. The five-vertex path · arXiv:2312.15333 [preprint, chưa bình duyệt]