Turan Problems and Shadows III: expansions of graphs

Abstract

The expansion $G^{+}$ of a graph $G$ is the $3$-uniform hypergraph obtained from $G$ by enlarging each edge of $G$ with a new vertex disjoint from $V(G)$ such that distinct edges are enlarged by distinct vertices. Let $e{x}_3(n,F)$ denote the maximum number of edges in a $3$-uniform hypergraph with $n$ vertices not containing any copy of a $3$-uniform hypergraph $F$. The study of $e{x}_3(n,G^{+})$ includes some well-researched problems, including the case that $F$ consists of $k$ disjoint edges, $G$ is a triangle, $G$ is a path or cycle, and $G$ is a tree. In this paper we initiate a broader study of the behavior of $e{x}_3(n,G^{+})$. Specifically, we show \[ ex_3(n,K_{s,t}^+) = Θ(n^{3 - 3/s})\] whenever $t>(s-1)!$ and $s\ge 3$. One of the main open problems is to determine for which graphs $G$ the quantity $e{x}_3(n,G^{+})$ is quadratic in $n$. We show that this occurs when $G$ is any bipartite graph with Turán number $o(n^{\phi })$ where $\phi =\frac{1+\sqrt{5}}{2}$, and in particular, this shows $e{x}_3(n,Q^{+})=\Theta (n^2)$ where $Q$ is the three-dimensional cube graph.

References in corpus (1)

• Hypergraph Turan numbers of linear cycles