Optimal sparse blow-up conjecture for bounded-bandwidth graphs

For each γ>0\gamma>0, Δ2\Delta\ge2, and k1k\ge1, there should exist constants β>0\beta^\ast>0 and C>0C^\ast>0 such that, asymptotically almost surely for Γ=G(n,p)\Gamma=G(n,p) whenever pCn2/(Δ+2)p\ge C^\ast n^{-2/(\Delta+2)}, every spanning subgraph GG of Γ\Gamma with

δ(G)(k1k+γ)pn\delta(G)\ge\left(\frac{k-1}{k}+\gamma\right)pn

and every kk-colourable graph HH on nn vertices with Δ(H)Δ\Delta(H)\le\Delta, bandwidth at most βn\beta^\ast n, at least Cp2C^\ast p^{-2} vertices not contained in any triangles, and at least Cp(Δ+2)(Δ1)/2n2ΔC^\ast p^{-(\Delta+2)(\Delta-1)/2}n^{2-\Delta} vertices not contained in any KΔ+1K_{\Delta+1}, satisfy the following. Sparse blow-up conjecture. The graph GG contains a copy of HH. This conjecture proposes the expected optimal lower bound on pp, accounting for the necessary obstructions caused by vertices of HH outside triangles and copies of KΔ+1K_{\Delta+1}.

Sources & referencesView supporting material

Primary source

Peter Allen, Julia Böttcher, Julia Ehrenmüller and Anusch Taraz, “The Bandwidth Theorem in Sparse Graphs”, arXiv:1612.00661 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.