Abstract
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 Furedi, J. Combin. Theory Ser. A, 45 (1987), pp. 226-262, generalizing the Erdos-Sos conjecture for trees, asserts that if T is a tight r-tree with t edges and G is an n-vertex r-uniform hypergraph containing no copy of T, then G has at most t-1/r(n/r-1 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 Ser. 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.
Original language | English (US) |
---|---|
Pages (from-to) | 862-873 |
Number of pages | 12 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 33 |
Issue number | 2 |
DOIs | |
State | Published - 2019 |
Keywords
- Hypergraph
- Kalai
- Tight tree
- Turan
ASJC Scopus subject areas
- General Mathematics