Partite Turán-densities for complete r-uniform hypergraphs on r+1 vertices
share
In this paper we investigate density conditions for finding a complete r-uniform hypergraph K_r+1^(r) on r+1 vertices in an (r+1)-partite r-uniform hypergraph G. First we prove an optimal condition in terms of the densities of the (r+1) induced r-partite subgraphs of G. Second, we prove a version of this result where we assume that r-tuples of vertices in G have their neighbours evenly distributed in G. Third, we also prove a counting result for the minimum number of copies of K_r+1^(r) when G satisfies our density bound, and present some open problems. A striking difference between the graph, r=2, and the hypergraph, r ≥ 3 , cases is that in the first case both the existence threshold and the counting function are non-linear in the involved densities, whereas for hypergraphs they are given by a linear function. Also, the smallest density of the r-partite parts needed to ensure the existence of a complete r-graph with (r+1) vertices is equal to the golden ratio τ=0.618... for r=2, while it is r/r+1for r≥3.
READ FULL TEXT