Triangle-free Subgraphs of Hypergraphs

Abstract

In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e\cap f|=|f\cap g|=|g\cap e|=1$ and $e\cap f\cap g=\varnothing$. We prove that if $H$ is an $n$-vertex $r$-uniform hypergraph with maximum degree $△$, then as $△\to \infty$, the number of edges in a densest $T$-free subhypergraph of $H$ is at least \[ \frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.\] For $r=3$, this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$-vertex triple system with edge-probability $p$ such that $p{n}^3\to \infty$ as $n\to \infty$, then with high probability as $n\to \infty$, the number of edges in a densest $T$-free subhypergraph is \[ \min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.\] We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.

Small typos were corrected