Hypergraphs not containing a tight tree with a bounded trunk

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 [Kalai], generalizing the ErdH{o}s-S'os 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

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 g e 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 [FF] from 1987. 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 [Katona].

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Hypergraphs not containing a tight tree with a bounded trunk