Abstract
A tight r-tree T is an r-uniform hypergraph that has an edge-ordering e1,e2,…,et such that for each i≥2, ei has a vertex vi that does not belong to any previous edge and ei−vi is contained in ej for some j<i. Kalai conjectured in 1984 that every n-vertex r-uniform hypergraph with more than [Formula presented] edges contains every tight r-tree T with t edges. A trunk T′ of a tight r-tree T is a tight subtree T′ of T such that vertices in V(T)∖V(T′) are leaves in T. Kalai's Conjecture was proved (Frankl and Füredi, 1987) for tight r-trees that have a trunk of size one. In a previous paper (Füredi et al., 2019) we proved an asymptotic version for all tight r-trees that have a trunk of bounded size. In this paper we continue that work to establish the exact form of Kalai's Conjecture for all tight 3-trees of at least 8 edges that have a trunk of size two.
Original language | English (US) |
---|---|
Pages (from-to) | 50-59 |
Number of pages | 10 |
Journal | Discrete Applied Mathematics |
Volume | 276 |
DOIs | |
State | Published - Apr 15 2020 |
Keywords
- Extremal hypergraph theory
- Hypergraph trees
- Turán problem
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics