TOPICS
Search

Intersecting Family

An intersecting family is a family F of sets such that A intersection B!=⌀ for every A,B in F. A k-uniform intersecting family has |A|=k for every A in F. A hitting set, also called a cover, meets every member of F. The minimum size of such a hitting set is the covering number tau(F).

Extremal sizes of intersecting families can change when the covering number is prescribed. The Frankl-Ota-Tokushige conjecture concerns the largest number of minimum hitting sets in a uniform intersecting family (Patkós 2026).

Another extremal parameter is the maximum size m(k) of a k-uniform intersecting family with covering number k. Frankl et al. (2026) proved

m(k)>=k^kexp(-50sqrt(klnk))

for lnk>=32. Combined with the upper bound of Zakharov (2024), this gives

m(k)=k^kexp(-k^(1/2+o(1)))

as k->infty. The notation o(1) denotes little-o notation. This refutes a separate conjecture of Frankl, Ota, and Tokushige asserting m(k)<(ck)^k for some fixed c<1 and all sufficiently large k (Frankl et al. 2026).

See also

Frankl-Ota-Tokushige Conjecture, Hitting Set, Hypergraph

Explore with Wolfram|Alpha

References

Erdős, P.; Ko, C.; and Rado, R. "Intersection Theorems for Systems of Finite Sets." Quart. J. Math. Oxford Ser. 12, 313-320, 1961. https://doi.org/10.1093/qmath/12.1.313.Frankl, P.; Wang, J.; Yang, Y.; and Zhang, Y. "The Maximum Size of Intersecting k-Graphs with Covering Number k." 27 Oct 2026. https://arxiv.org/abs/2610.37315.Patkós, B. "Intersecting Families with Large Covering Number-On a Conjecture of Frankl, Ota, and Tokushige." 20 Oct 2026. https://arxiv.org/abs/2610.28029.Zakharov, D. "On the Size of Maximal Intersecting Families." Combin. Probab. Comput. 33, 32-49, 2024.

Cite this as:

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

Subject classifications