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.

A separate conjecture of the same authors concerns the maximum size m(k) of a k-uniform intersecting family with covering number k. It asserts that m(k)<(ck)^k for some fixed c<1 and all sufficiently large k. Frankl et al. (2026) refuted this assertion by proving m(k)>=k^kexp(-50sqrt(klnk)) for lnk>=32. This is distinct from the fixed-t question about numbers of minimum hitting sets. Frankl et al. (2026) attribute the new construction to generative AI and its verification to the authors.

See also

Hitting Set, Intersecting Family

Explore with Wolfram|Alpha

References

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.

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