2020/02/18 by Zoltan Furedi, Furedi, Zoltan, Ruth Luo +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2002.07350
arxiv created 2020/02/18 · arxiv updated 2020/02/19
Let F be a graph. We say that a hypergraph H contains an induced Berge F if the vertices of F can be embedded to H (e.g., V(F)⊆ V(H)) and there exists an injective mapping f from the edges of F to the hyperedges of H such that f(xy) ∩ V(F) = \x,y\ holds for each edge xy of F. In other words, H contains F as a trace. Let exr(n,Bind F) denote the maximum number of edges in an r-uniform hypergraph with no induced Berge F. Let ex(n,Kr, F) denote the maximum number of Kr's in an F-free graph on n vertices. We show that these two Turán type functions are strongly related.