TOPICS
Search

Kalai's Conjecture for Tight Trees


Kalai's conjecture (Frankl and Füredi 1987) states that, for n>=r>=2, t>=1, and every tight tree T with t hyperedges,

 ex(n,T)<=(t-1)/r(n; r-1),

where ex(n,T) is the maximum number of hyperedges in an n-vertex r-uniform hypergraph containing no copy of T. When r=2, the statement is the Erdős-Sós conjecture.

Mubayi and Verstraëte (2026) proved the stronger hypergraph shadow bound

 |E(H)|<=(t-1)/r|partialH|<=(t-1)/r(n; r-1).

The bound is attained for infinitely many n. The authors report that GPT-6 Astra found the proof and that they checked and rewrote it. Independent external review had not been reported as of Sep. 23, 2026.


See also

Hypergraph, Hypergraph Shadow, Tight Tree

Explore with Wolfram|Alpha

References

Frankl, P. and Füredi, Z. "Exact Solution of Some Turán-Type Problems." J. Combin. Theory Ser. A 45, 226-262, 1987. https://doi.org/10.1016/0097-3165(87)90016-1.Mubayi, D. and Verstraëte, J. "Kalai's Conjecture for Tight Trees." 7 Sep 2026. https://arxiv.org/abs/2609.08012.

Cite this as:

Weisstein, Eric W. "Kalai's Conjecture for Tight Trees." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KalaisConjectureforTightTrees.html

Subject classifications