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).

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.


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