The Turan density problem for hypergraphs

Given a $k$-graph $H$ a complete blow-up of $H$ is a $k$-graph $\hat{H}$ formed by replacing each $v \in V (H)$ by a non-empty vertex class $A_v$ and then inserting all edges between any $k$ vertex classes corresponding to an edge of $H$. Given a subgraph $G \subseteq \hat{H}$ and an edge $e \in E(H)$ we define the density $d_e (G)$ to be the proportion of edges present in $G$ between the classes corresponding to $e$.

The density Turán problem for $H$ asks: determine the minimal value $d_\mathrm{crit} (H)$ such that any subgraph $G \subseteq \hat{H}$ satisfying $d_e (G) \gt d_\mathrm{crit} (H)$ for every $e \in E(H)$ contains a copy of $H$ as a transversal, i.e. a copy of $H$ meeting each vertex class of $\hat{H}$ exactly once. We give upper bounds for this hypergraph density Turán problem that generalise the known bounds for the case of graphs due to Csikvári and Nagy [3], although our methods are different, employing an entropy compression argument.

Keywords

transversals, entropy compression

2010 Mathematics Subject Classification

Primary 05D05. Secondary 05D40.

The full text of this article is unavailable through your IP address: 18.227.102.205

Received 2 July 2020

Accepted 2 August 2021

Published 18 August 2022