Kalai's Conjecture for Tight Trees
Abstract
Let r ≥ 2 and t ≥ 1. It is shown that if T is an r-uniform tight tree with t edges and H is a T-free r-uniform hypergraph, then |E(H)|≤ (t−1)|sh H|/r, where sh H is the (r−1)-shadow of H. \iffalse Equality holds only for (n,t + r − 2,r)-designs.\fi The bound is tight infinitely often, and establishes Kalai's Conjecture, whose r=2 case is the Erd\H os-Sós Conjecture. The proof was found by GPT-6 Astra, extending its method of proof for the Erd\H os-Sós conjecture to the hypergraph setting. It is noteworthy that previous proofs of special cases of the Erd\H os-Sós conjecture do not extend to give tights bounds in the hypergraph setting. A strengthening of the Erd\H os-Sós conjecture due to the authors about tight lower bounds on the number of copies of a tree in a graph with average degree d ≥ t−1≥ 0 remains open.
Related
- Fractional expectation thresholds and the "second" Kahn-Kalai conjecture
- Prescribed Color Patterns in Tight Hamilton Cycles and Spanning Trees
- A Tight Fractional Version of Generalized Tuza's Conjecture
- Quantum percolation conjecture on regular trees
- Tight instances of the Lonely Runner Conjecture: one-entry modifications and the growth of speeds
BibTeX
@misc{mubayi2026kalais,
title = {{Kalai's Conjecture for Tight Trees}},
author = {Dhruv Mubayi and Jacques Verstraete},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08012},
eprint = {2609.08012},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08012},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Kalai's Conjecture for Tight Trees
AU - Dhruv Mubayi
AU - Jacques Verstraete
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.08012
UR - https://arxiv.org/abs/2609.08012
AB - Let r ≥ 2 and t ≥ 1. It is shown that if T is an r-uniform tight tree with t edges and H is a T-free r-uniform hypergraph, then |E(H)|≤ (t−1)|sh H|/r, where sh H is the (r−1)-shadow of H. \iffalse Equality holds only for (n,t + r − 2,r)-designs.\fi The bound is tight infinitely often, and establishes Kalai's Conjecture, whose r=2 case is the Erd\H os-Sós Conjecture. The proof was found by GPT-6 Astra, extending its method of proof for the Erd\H os-Sós conjecture to the hypergraph setting. It is noteworthy that previous proofs of special cases of the Erd\H os-Sós conjecture do not extend to give tights bounds in the hypergraph setting. A strengthening of the Erd\H os-Sós conjecture due to the authors about tight lower bounds on the number of copies of a tree in a graph with average degree d ≥ t−1≥ 0 remains open.
ER -