Embedding tetrahedra into quasirandom hypergraphs

Abstract

We investigate extremal problems for quasirandom hypergraphs. We say that a $3$-uniform hypergraph $H=(V,E)$ is $(d,\eta )$-quasirandom if for any subset $X\subseteq V$ and every set of pairs $P\subseteq V\times V$ the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being a hyperedge of $H$ is in the interval $d|X||P|\pm \eta |V{|}^3$. We show that for any $\epsilon >0$ there exists $\eta >0$ such that every sufficiently large $(1/2+\epsilon ,\eta )$-quasirandom hypergraph contains a tetrahedron, i.e., four vertices spanning all four hyperedges. A known random construction shows that the density $1/2$ is best possible. This result is closely related to a question of Erdős, whether every weakly quasirandom $3$-uniform hypergraph $H$ with density bigger than $1/2$, i.e., every large subset of vertices induces a hypergraph with density bigger than $1/2$, contains a tetrahedron.

18 pages, second version addresses changes arising from the referee reports

Cited by in corpus (6)

• Extremal problems in uniformly dense hypergraphs
• Hypergraphs with vanishing Turán density in uniformly dense hypergraphs
• On a generalisation of Mantel's theorem to uniformly dense hypergraphs
• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm
• Counting results for sparse pseudorandom hypergraphs II
• Hypergraphs with uniform Turán density equal to 8/27