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

Giả thuyết họ tập đóng với phép hợp (Frankl)

Còn mở

Cho $\mathcal{F}$ là một họ hữu hạn các tập hợp hữu hạn, không chỉ gồm mỗi tập rỗng $\mathcal{F} \neq \{\emptyset\}$ , và đóng với phép hợp (với mọi $A, B \in \mathcal{F}$ , hợp của chúng $A \cup B \in \mathcal{F}$ ). Khi đó tồn tại một phần tử $x$ thuộc tập nền $\bigcup_{A \in \mathcal{F}} A$ nằm trong ít nhất một nửa số tập của $\mathcal{F}$ , tức là $\#\{A \in \mathcal{F} : x \in A\} \ge \frac{1}{2} |\mathcal{F}|$ .

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

Tính đến năm 2026, giả thuyết $\frac{1}{2}$ của Frankl vẫn còn mở, với cận dưới hằng số tổng quát tốt nhất đứng ngay trên ngưỡng $\frac{3 - \sqrt{5}}{2} \approx 0.38197$ (đạt $\approx 0.38234$ , Yu, 2023). Đáng chú ý, Sawin và Alweiss–Huang–Sellke chỉ ra rằng $\frac{3 - \sqrt{5}}{2}$ chính là rào cản tự nhiên cho phương pháp entropy độc lập cùng phân bố của Gilmer vì các phân bố đóng xấp xỉ với phép hợp đạt dấu bằng tại đó. Để vươn tới $\frac{1}{2}$ cần khai thác tính nguyên tổ hợp chính xác của $\mathcal{F}$ vượt ra ngoài phép so sánh entropy bậc nhất.

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

Mọi họ hữu hạn đóng với phép hợp $\mathcal{F} \neq \{\emptyset\}$ đều có một phần tử với tần suất ít nhất $\frac{3 - \sqrt{5}}{2} \approx 0.38197$ (Alweiss–Huang–Sellke, Chase–Lovett, Pebody và Sawin, 2022, tiếp nối Gilmer), sau được tinh chỉnh lên $\approx 0.38234$ (2023).
Giả thuyết $\frac{1}{2}$ đầy đủ đúng cho mọi họ đóng với phép hợp trên tập nền có kích thước $n \le 12$ và các họ có $|\mathcal{F}| \le 50$ (Bošnjak–Marković, 2008; Roberts–Simpson, 2010).

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

Công cụ	Đạt được	Chỗ dừng
Entropy Shannon của các tập con ngẫu nhiên độc lập (phương pháp Gilmer)	Lấy mẫu $A, B \in \mathcal{F}$ độc lập để $A \cup B \in \mathcal{F}$ và dùng tính dưới môđun của entropy có điều kiện để chứng minh $H(A \cup B) > H(A)$ nếu mọi xác suất biên đều nhỏ hơn $\frac{3 - \sqrt{5}}{2}$ , dẫn tới mâu thuẫn.	Với phân bố tích hai trạng thái nơi mỗi tọa độ bằng $1$ với xác suất $p > \frac{3 - \sqrt{5}}{2}$ , entropy nhị phân thỏa mãn $h(2p - p^2) \le h(p)$ , chặn đứng phương pháp một phân bố tại $\frac{3 - \sqrt{5}}{2}$ .
Lấy trung bình trọng số và quy giản cấu hình địa phương	Chứng minh cận $\frac{1}{2}$ bất cứ khi nào $\mathcal{F}$ chứa các tập nhỏ cỡ $1$ hoặc $2$ , hoặc khi $\|\mathcal{F}\|$ lớn so với kích thước tập nền $n$ .	Không áp dụng được khi kích thước tập khác rỗng nhỏ nhất trong $\mathcal{F}$ tăng theo $n$ và $\|\mathcal{F}\|$ chỉ tăng đa thức hoặc dưới hàm mũ theo $n$ .

Câu hỏi còn mở

Liệu mọi họ tập hữu hạn đóng với phép hợp $\mathcal{F} \neq \{\emptyset\}$ có đều chứa một phần tử thuộc ít nhất $\frac{1}{2} |\mathcal{F}|$ tập hay không?
Liệu các bất đẳng thức lý thuyết thông tin đa mẫu hoặc bậc cao có thể vượt xa rào cản $\frac{3 - \sqrt{5}}{2}$ để tiến gần tới $\frac{1}{2}$ hay không?

Tài liệu tham khảo

Justin Gilmer (2022). A constant lower bound for the union-closed sets conjecture · arXiv:2211.09055 [preprint, chưa bình duyệt]
Henning Bruhn, Oliver Schaudt (2015). The journey of the union-closed sets conjecture · DOI:10.1007/s00373-014-1515-0