Relative Turán Problems for Uniform Hypergraphs

Abstract

For two graphs $F$ and $H$, the relative Turán number $\mathrm{ex}(H,F)$ is the maximum number of edges in an $F$-free subgraph of $H$. Foucaud, Krivelevich, and Perarnau \cite{FKP} and Perarnau and Reed \cite{PR} studied these quantities as a function of the maximum degree of $H$. In this paper, we study a generalization for uniform hypergraphs. If $F$ is a complete $r$-partite $r$-uniform hypergraph with parts of sizes $s_1,s_2,\dots ,s_r$ with each $s_{i+1}$ sufficiently large relative to $s_i$, then with $1/\beta ={\sum }_{i=2}^r{\prod }_{j=1}^{i-1}{s}_j$ we prove that for any $r$-uniform hypergraph $H$ with maximum degree $\Delta$, \[\mathrm{ex}(H,F)\ge Δ^{-β- o(1)} \cdot e(H).\] This is tight as $\Delta \to \infty$ up to the $o(1)$ term in the exponent, since we show there exists a $\Delta$-regular $r$-graph $H$ such that $\mathrm{ex}(H,F)=O({\Delta }^{-\beta })\cdot e(H)$. Similar tight results are obtained when $H$ is the random $n$-vertex $r$-graph $H_{n,p}^r$ with edge-probability $p$, extending results of Balogh and Samotij \cite{BS} and Morris and Saxton \cite{MS}.

22 pages

References in corpus (3)

• Large subgraphs without short cycles
• Existence of spanning $\mathcal{F}$-free subgraphs with large minimum degree
• Norm hypergraphs