Back to Search Start Over

Turán number of special four cycles in triple systems

Authors :
András Gyárfás
Attila Sali
Zoltán Füredi
Source :
Discrete Mathematics. 345:112667
Publication Year :
2022
Publisher :
Elsevier BV, 2022.

Abstract

A special four-cycle F in a triple system consists of four triples 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 ( 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 F . Our main result implies that the Turan number ex ( n , F ) = Θ ( n 3 / 2 ) . In fact, we prove more, ex ( n , { F 1 , F 2 , F 3 } ) = Θ ( n 3 / 2 ) , where the F i -s are specific members of F . This extends previous bounds for the Turan number of triple systems containing no Berge four cycles. We also study ex ( n , A ) for all A ⊆ F . For 16 choices of A we show that e x ( n , A ) = Θ ( n 3 / 2 ) , for 92 choices of A we find that ex ( n , A ) = Θ ( n 2 ) and the other 18 cases remain unsolved.

Details

ISSN :
0012365X
Volume :
345
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi...........30cb07910991829b52a97404d6b7567f
Full Text :
https://doi.org/10.1016/j.disc.2021.112667