TOPICS
Search

Frankl-Ota-Tokushige Conjecture

The Frankl-Ota-Tokushige conjecture concerns the number of minimum hitting sets of a uniform intersecting family. Let p_t(k) be the largest number of t-element hitting sets of a k-uniform intersecting family whose covering number is t. The ground set may be any finite set. For a fixed integer t>=2, write

p_t(k)=k^t-b(t)k^(t-1)+O_t(k^(t-2))

as k->infty, where O denotes big-O notation. The conjecture states b(t)=(t; 2) (Patkós 2026).

Patkós (2026) refuted the conjecture by proving

b(t)<=2sqrt(2)t^(3/2)sqrt(lnt)+O(t^(3/2)).

He also established the lower bound b(t)>=2t^(3/2)/3^(3/4)-O(t). Patkós (2026) attributes the counterexample construction to ChatGPT and the lower-bound proof to himself.

See also

Hitting Set, Intersecting Family

Explore with Wolfram|Alpha

References

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.

Cite this as:

Weisstein, Eric W. "Frankl-Ota-Tokushige Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Frankl-Ota-TokushigeConjecture.html

Subject classifications