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

Giả thuyết hoa hướng dương Erdős–Rado

Còn mởErdős

Với mọi số nguyên $r \ge 3$ , tồn tại một hằng số $C_r > 0$ chỉ phụ thuộc vào $r$ sao cho mọi họ tập hợp $\mathcal{F}$ gồm các tập có lực lượng tối đa $w$ thỏa mãn $|\mathcal{F}| \ge C_r^w$ đều chứa một hoa hướng dương $r$ cánh (hay hệ $\Delta$ ) — tức là $r$ tập phân biệt $S_1, \dots, S_r \in \mathcal{F}$ có giao từng đôi đều bằng cùng một phần lõi chung $K$ ( $S_i \cap S_j = K$ với mọi $i \neq j$ ).

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

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

Tính đến năm 2026, cận trên tốt nhất được biết cho bài toán hoa hướng dương $r$ cánh trên các họ tập $w$ -đồng nhất là $|\mathcal{F}| \ge (C r \log w)^w$ (Bell–Chueluecha–Warnke, 2021, tiếp nối Alweiss–Lovett–Wu–Zhang, 2019 và Rao, 2020). Cận này đúng cho khái niệm mạnh hơn là hoa hướng dương xấp xỉ (vững) tham số $(1/r, 1/r)$ , mà đối với khái niệm đó thì nhân tử $\log w$ thực sự là chặt. Do đó, việc loại bỏ nhân tử $\log w$ còn lại để đạt tới $C_r^w$ ngay cả khi $r = 3$ đòi hỏi những lập luận phân biệt được tính rời nhau chính xác của các cánh hoa với tính rời nhau xác suất.

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

Mọi họ gồm các tập $w$ phần tử có kích thước $|\mathcal{F}| \ge (C r \log w)^w$ đều chứa một hoa hướng dương $r$ cánh (Alweiss–Lovett–Wu–Zhang, 2019; Rao, 2020; Bell–Chueluecha–Warnke, 2021).
Giả thuyết hoa hướng dương yếu trong $\{0, 1\}^n$ (hoặc hoa hướng dương trong $\mathbb{F}_3^n$ ) đã được chứng minh với cận hàm mũ $c^n$ ( $c < 2$ ) bằng phương pháp đa thức hạng lát cắt (Naslund và Sawin, 2017).

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

Công cụ	Đạt được	Chỗ dừng
Hệ tập κ-trải rộng và mã hóa entropy Shannon	Quy các họ tổng quát về họ $\kappa$ -trải rộng (nơi không có tập con khác rỗng nào nằm trong quá $\kappa^{-\|T\|} \|\mathcal{F}\|$ tập) và chứng minh một tập ngẫu nhiên mật độ $\frac{1}{2r}$ chứa một tập của $\mathcal{F}$ với xác suất gần $1$ , thu được cận $(C r \log w)^w$ .	Một tập ngẫu nhiên mật độ $\frac{1}{2r}$ chỉ phủ được tập cỡ $w$ khi tham số trải rộng thỏa mãn $\kappa = \Omega(r \log w)$ , khiến nhân tử $\log w$ không thể tránh khỏi đối với hoa hướng dương vững.
Phương pháp đa thức hạng lát cắt	Chứng minh cận hàm mũ $(3 / 2^{2/3})^n \approx 1.8899^n$ cho các tập con không chứa hoa hướng dương của $\{0, 1\}^n$ khi kích thước tập nền $n$ cố định.	Cận phụ thuộc hàm mũ vào kích thước vũ trụ nền $n$ chứ không phải kích thước tập $w$ , nên thất bại khi $n \gg w$ .

Câu hỏi còn mở

Có tồn tại hằng số tuyệt đối $C_3 > 0$ sao cho mọi họ các tập $w$ phần tử có kích thước ít nhất $C_3^w$ đều chứa một hoa hướng dương $3$ cánh hay không?
Liệu cận $(C r \log w)^w$ có thể được cải thiện thành $C_r^w (\log w)^{o(w)}$ khi cố định $r = 3$ hay không?

Tài liệu tham khảo

Paul Erdős, Richard Rado (1960). Intersection theorems for systems of sets · DOI:10.1112/jlms/s1-35.1.85
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang (2021). Improved bounds for the sunflower lemma · DOI:10.4007/annals.2021.194.3.5 · arXiv:1908.08483