Turan Problems and Shadows II: Trees

Abstract

The expansion $G^{+}$ of a graph $G$ is the 3-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let ex${}_r(n,F)$ denote the maximum number of edges in an $r$-uniform hypergraph with $n$ vertices not containing any copy of $F$. The authors \cite{KMV} recently determined ex${}_3(n,G^{+})$ more generally, namely when $G$ is a path or cycle, thus settling conjectures of Füredi-Jiang \cite{FJ} (for cycles) and Füredi-Jiang-Seiver \cite{FJS} (for paths). Here we continue this project by determining the asymptotics for ex${}_3(n,G^{+})$ when $G$ is any fixed forest. This settles a conjecture of Füredi \cite{Furedi}. Using our methods, we also show that for any graph $G$, either ex${}_3(n,G^{+})\le \left(\frac{1}{2}+o(1)\right)n^2$ or ex${}_3(n,G^{+})\ge (1+o(1))n^2,$ thereby exhibiting a jump for the Turán number of expansions.

References in corpus (1)

• Hypergraph Turan numbers of linear cycles