Non-degenerate Hypergraphs with Exponentially Many Extremal Constructions

Abstract

For every integer $t\ge 0$, denote by $F_5^t$ the hypergraph on vertex set $\{1,2,\dots ,5+t\}$ with hyperedges $\{123,124\}\cup \{34k:5\le k\le 5+t\}$. We determine $\mathrm{ex}(n,F_5^t)$ for every $t\ge 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üredi on the Turán number of $F_5:=F_5^0$. Our results extend a theory of Erdős and Simonovits about the extremal constructions for certain fixed graphs. In particular, the hypergraphs $F_5^{6t}$, for $t\ge 1$, are the first examples of hypergraphs with exponentially many extremal constructions and positive Turán density.