Hypergraphs not containing a tight tree with a bounded trunk. II: 3-trees with a trunk of size 2

Abstract: A tight

r

-tree

T

is an

r

-uniform hypergraph that has an edge-ordering

e_{1}, e_{2}, d o t s, e_{t}

such that for each

i g e q 2

,

e_{i}

has a vertex

v_{i}

that does not belong to any previous edge and

e_{i} - v_{i}

is contained in

e_{j}

for some

j < i

. Kalai conjectured in 1984 that every

n

-vertex

r

-uniform hypergraph with more than

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) s e t m i n u s V (T^{'})

are leaves in

T

. Kalai's Conjecture was proved in 1987 for tight

r

-trees that have a trunk of size one. In a previous paper we proved an asymptotic version of Kalai's Conjecture 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 with at least

20

edges that have a trunk of size two.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Hypergraphs not containing a tight tree with a bounded trunk. II: 3-trees with a trunk of size 2