Partite Tur\'an-densities for complete uniform hypergraphs on vertices
K Markström, C Thomassen - arXiv preprint arXiv:1903.04270, 2019 - arxiv.org
arXiv preprint arXiv:1903.04270, 2019•arxiv.org
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+ …
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+ …
In this paper we investigate density conditions for finding a complete -uniform hypergraph on vertices in an -partite -uniform hypergraph . First we prove an optimal condition in terms of the densities of the induced -partite subgraphs of . Second, we prove a version of this result where we assume that -tuples of vertices in have their neighbours evenly distributed in . Third, we also prove a counting result for the minimum number of copies of when satisfies our density bound, and present some open problems. A striking difference between the graph, , and the hypergraph, , 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 -partite parts needed to ensure the existence of a complete -graph with vertices is equal to the golden ratio for , while it is for .
arxiv.org