Turan number of special four cycles in triple systems


Abstract in English

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_iv_iv_{i+1}$ (indices are understood $pmod 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 $cal{F}$. Our main result implies that the Turan number $text{ex}(n,{cal{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 $cal{F}$. This extends previous bounds for the Turan number of triple systems containing no Berge four cycles. We also study $text{ex}(n,{cal{A}})$ for all ${cal{A}}subseteq {cal{F}}$. For 16 choices of $cal{A}$ we show that $text{ex}(n,{cal{A}})=Theta(n^{3/2})$, for 92 choices of $cal{A}$ we find that $text{ex}(n,{cal{A}})=Theta(n^2)$ and the other 18 cases remain unsolved.

Download