Hypergraphs not containing a tight tree with a bounded trunk

Zoltan Furedi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraete

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)862-873
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number2
DOIs
StatePublished - 2019

Keywords

  • Hypergraph
  • Kalai
  • Tight tree
  • Turan

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Hypergraphs not containing a tight tree with a bounded trunk'. Together they form a unique fingerprint.

Cite this