2017/05/11 by Gerbner, Dániel, Methuku, Abhishek, Vizer, Máté
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1705.04134
Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge of F by a hyperedge containing it. Let F be a family of graphs. The Turán number of Berge-F is the maximum possible number of edges in an r-uniform hypergraph on n vertices containing no Berge-F as a subhypergraph (for every F ∈ F) and is denoted by exr(n,F). We determine the asymptotics for the Turán number of Berge-K2,t by showing ex3(n,K2,t)=(1)/(6)(t-1)3/2 ⋅ n3/2(1+o(1)) for any given t ≥ 7. We study the analogous question for linear hypergraphs and show that ex3(n,\C2, K2,t\) = (1)/(6)√(t-1) ⋅ n3/2(1+ot(1)). We also prove general upper and lower bounds on the Turán numbers of a class of graphs including exr(n, K2,t), exr(n,\C2, K2,t\), and exr(n, C2k) for r ≥ 3. Our bounds improve results of Gerbner and Palmer, Füredi and Özkahya, Timmons, and provide a new proof of a result of Jiang and Ma.