Search

An r -uniform hypergraph is a tight r-tree if its edges can be ordered so that every edge e contains a vertex v that does not belong to any preceding edge and the set e - v lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Füredi, J. Combin. Theory Ser. A, 45 (1987), pp. 226--262, generalizing the Erdõs-Sós conjecture for trees, asserts that if T is a tight r -tree with t edge\bigr)s and G is an n-vertex r-uniform hypergraph containing no copy of T, then G has at most t--1/r(n r-i) edges. A trunk T' of a tight r-tree T is a tight subtree such that every edge of T - T' has r - 1 vertices in some edge of T' and a vertex outside T'. For r ≥ 3, the only nontrivial family of tight r-trees for which this conjecture has been proved is the family of r-trees with trunk size one in J. Combin. Theory Se r. A, 45 (1987), pp. 226--262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees T of bounded trunk size. This follows from our upper bound on the size of a T-free r-uniform hypergraph G in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight r-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length 4 implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329--337. [ABSTRACT FROM AUTHOR]