Turán number of special four cycles in triple systems

Abstract

A {\em special four-cycle } $F$ in a triple system consists of four triples {\em inducing } a $C_4$. This means that $F$ has four special vertices $v_1,v_2,v_3,v_4$ and four triples in the form $w_i{v}_i{v}_{i+1}$ (indices are understood $(\mathrm{mod}4)$) where the $w_j$s are not necessarily distinct but disjoint from $\{v_1,v_2,v_3,v_4\}$. There are seven non-isomorphic special four-cycles, their family is denoted by $\mathcal{F}$. Our main result implies that the Turán number $\text{ex}(n,\mathcal{F})=\Theta (n^{3/2})$. In fact, we prove more, $\text{ex}(n,\{F_1,F_2,F_3\})=\Theta (n^{3/2})$, where the $F_i$-s are specific members of $\mathcal{F}$. This extends previous bounds for the Turán number of triple systems containing no Berge four cycles. We also study $\text{ex}(n,\mathcal{A})$ for all $\mathcal{A}\subseteq \mathcal{F}$. For 16 choices of $\mathcal{A}$ we show that $\text{ex}(n,\mathcal{A})=\Theta (n^{3/2})$, for 92 choices of $\mathcal{A}$ we find that $\text{ex}(n,\mathcal{A})=\Theta (n^2)$ and the other 18 cases remain unsolved.

7 figures