Partite Turán-densities for complete $r$-uniform hypergraphs on $r+1$ vertices

In this paper we investigate density conditions for finding a complete $r$-uniform hypergraph $K^{(r)}_{r+1}$ 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)}_{r+1}$ when $G$ satisfies our density bound, and present some open problems.

A striking difference between the graph, $r=2$, and the hypergraph, $r \geq 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 $\tau = 0.618 \dotsc$ for $r=2$, while it is $\frac{r}{r+1}$ for $r \geq 3$.

Keywords

Turan problem, mulitpartite, hypergraph

2010 Mathematics Subject Classification

Primary 05C35. Secondary 05C30.

Full Text (PDF format)

The first author was supported by The Swedish Research Council grant 2014–4897. The second author was supported by ERC Advanced Grant GRACOL.

Received 11 March 2019

Accepted 6 May 2020

Published 16 July 2021