2021/03/17 by Zoltán Füredi, Füredi, Zoltán, András Gyárfás +3
Engineering · Computer Science · Mathematics · #graph theory and CDMA systems #Coding theory and cryptography #Advanced Differential Equations and Dynamical Systems
paper · pdf · doi:10.48550/arxiv.2103.09774
A \em special four-cycle F in a triple system consists of four triples \em inducing a C4. This means that F has four special vertices v1,v2,v3,v4 and four triples in the form wivivi+1 (indices are understood \pmod 4) where the wjs are not necessarily distinct but disjoint from \v1,v2,v3,v4\. There are seven non-isomorphic special four-cycles, their family is denoted by \calF. Our main result implies that the Turán number ex(n,\calF)=Θ(n3/2). In fact, we prove more, ex(n,\F1,F2,F3\)=Θ(n3/2), where the Fi-s are specific members of \calF. This extends previous bounds for the Turán number of triple systems containing no Berge four cycles. We also study ex(n,\calA) for all \calA⊆ \calF. For 16 choices of \calA we show that ex(n,\calA)=Θ(n3/2), for 92 choices of \calA we find that ex(n,\calA)=Θ(n2) and the other 18 cases remain unsolved.