2020/09/04 by Spiro, Sam, Verstraëte, Jacques
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2009.02416
For two graphs F and H, the relative Turán number ex(H,F) is the maximum number of edges in an F-free subgraph of H. Foucaud, Krivelevich, and Perarnau \citeFKP and Perarnau and Reed \citePR 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 s1,s2,…,sr with each si + 1 sufficiently large relative to si, then with 1/β= ∑i = 2r ∏j = 1i - 1 sj we prove that for any r-uniform hypergraph H with maximum degree Δ, ex(H,F)≥ Δ-β- o(1) ⋅ e(H). This is tight as Δ→ ∞ up to the o(1) term in the exponent, since we show there exists a Δ-regular r-graph H such that ex(H,F)=O(Δ-β) ⋅ e(H). Similar tight results are obtained when H is the random n-vertex r-graph Hn,pr with edge-probability p, extending results of Balogh and Samotij \citeBS and Morris and Saxton \citeMS.