← All problems

Strong Erdős–Frankl–Füredi cover-free conjecture

For an integer r≥1r\ge 1, let T(r)T(r) be the least integer nn for which there exists a family F\mathcal{F} of nonempty subsets of an nn-element set such that ∣F∣>n|\mathcal{F}|>n and, for every choice of distinct sets A0,A1,…,Ar∈FA_0,A_1,\ldots,A_r\in\mathcal{F}, A0⊈⋃i=1rAiA_0\not\subseteq\bigcup_{i=1}^r A_i. The conjecture asserts that T(r)≥(r+1)2T(r)\ge (r+1)^2 for every integer r≥1r\ge 1.

References

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to settle the conjecture, but the claim has not been independently checked.

The conjecture concerns the exact threshold for the first nontrivial rr-cover-free family, namely whether T(r)≥(r+1)2T(r)\ge (r+1)^2 for every positive integer rr. The retrieved record includes an earlier result proving only the asymptotic form, so the new claim is the first directly relevant assertion of a complete solution.

October 17, 2026 claimed proof

Yanan Hu and Leilei Zhang claim in an unrefereed preprint that the universal lower bound for the strong conjecture holds for all positive integers rr, which would settle the conjecture and recover equality in the prime-power cases. A separate recent preprint proves T(r)≥r2+r+2T(r)\ge r^2+r+2 and T(r)=(1+o(1))r2T(r)=(1+o(1))r^2, but explicitly says that T(r)≥(r+1)2T(r)\ge (r+1)^2 remains unsettled; the relationship between these records is unresolved in the retrieved material.

Current status (as of October 2026): A preprint claims the strong conjecture is solved, but the claim is unverified; the exact bound T(r)≥(r+1)2T(r)\ge (r+1)^2 is not independently established in the retrieved evidence.

Sources

Solutions 0

No solutions have been posted yet.