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.

Full Text (PDF format)

Received 2 July 2020

Accepted 2 August 2021

Published 18 August 2022