Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions

Abstract: For every integer

t g e 0

, denote by

F_{5}^{t}

the hypergraph on vertex set

1, 2, l d o t s, 5 + t

with hyperedges

123, 124 c u p 34 k : 5 l e k l e 5 + t

. We determine

m a t h r m e x (n, F_{5}^{t})

for every

t g e 0

and sufficiently large

n

and characterize the extremal

F_{5}^{t}

-free hypergraphs. In particular, if

n

satisfies certain divisibility conditions, then the extremal

F_{5}^{t}

-free hypergraphs are exactly the balanced complete tripartite hypergraphs with additional hyperedges inside each of the three parts

(V_{1}, V_{2}, V_{3})

in the partition; each part

V_{i}

spans a

(| V_{i} |, 3, 2, t)

-design. This generalizes earlier work of Frankl and F"uredi on the Tur'an number of

F_{5} := F_{5}^{0}

. Our results extend a theory of ErdH{o}s and Simonovits about the extremal constructions for certain fixed graphs. In particular, the hypergraphs

F_{5}^{6 t}

, for

t g e q 1

, are the first examples of hypergraphs with exponentially many extremal constructions and positive Tur'an density.

This page was built for publication: Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions