New bounds for a hypergraph bipartite Turán problem

Abstract Let t be an integer such that t ≥ 2 . Let K 2 , t ( 3 ) denote the triple system consisting of the 2t triples { a , x i , y i } , { b , x i , y i } for 1 ≤ i ≤ t , where the elements a , b , x 1 , x 2 , … , x t , y 1 , y 2 , … , y t are all distinct. Let ex ( n , K 2 , t ( 3 ) ) denote the maximum size of a triple system on n elements that does not contain K 2 , t ( 3 ) . This function was studied by Mubayi and Verstraete [9] , where the special case t = 2 was a problem of Erdős [1] that was studied by various authors [3] , [9] , [10] . Mubayi and Verstraete proved that ex ( n , K 2 , t ( 3 ) ) t 4 ( n 2 ) and that for infinitely many n, ex ( n , K 2 , t ( 3 ) ) ≥ 2 t − 1 3 ( n 2 ) . These bounds together with a standard argument show that g ( t ) : = lim n → ∞ ⁡ ex ( n , K 2 , t ( 3 ) ) / ( n 2 ) exists and that 2 t − 1 3 ≤ g ( t ) ≤ t 4 . Addressing the question of Mubayi and Verstraete on the growth rate of g ( t ) , we prove that as t → ∞ , g ( t ) = Θ ( t 1 + o ( 1 ) ) .