TOPICS
Search

Cover-Free Family


A cover-free family of parameter r, or r-cover-free family, is a family F of distinct nonempty sets such that no member is contained in the union of at most r other members. This condition limits how efficiently the members can cover one another (Huang and Liu 2026).

Let T(r) be the least size n of a ground set admitting an r-cover-free family with more than n members. Huang and Liu (2026) proved

 T(r)>=r^2+r+2

for every integer r>=1. Together with the known upper bound from affine planes, this gives T(r)=(1+o(1))r^2 as r->infty, resolving the asymptotic Erdős-Frankl-Füredi conjecture (Huang and Liu 2026). This asymptotic result does not give an exact formula for T(r). Huang and Liu (2026) state that the mathematical ideas and proofs are their own, while an AI tool suggested a simplification of calculations.

Hu and Zhang (2026) strengthened the lower bound to

 T(r)>=(r+1)^2

for every integer r>=1, proving the strong Erdős-Frankl-Füredi cover-free conjecture. The affine plane construction attains this value whenever r+1 is a prime power, so T(r)=(r+1)^2 in those cases. Hu and Zhang (2026) report AI assistance during early proof development.


See also

Affine Plane, Antichain, Family, Union

Explore with Wolfram|Alpha

References

Hu, Y. and Zhang, L. "A Proof of the Strong Erdős-Frankl-Füredi Cover-Free Conjecture." 17 Oct 2026. https://arxiv.org/abs/2610.24442.Huang, X. and Liu, H. "The Asymptotic Erdős-Frankl-Füredi Cover-Free Conjecture." 15 Oct 2026. https://arxiv.org/abs/2610.22021.

Cite this as:

Weisstein, Eric W. "Cover-Free Family." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Cover-FreeFamily.html

Subject classifications