Optimal sparse blow-up conjecture for bounded-bandwidth graphs

About 10 years old · traced to

For each γ>0\gamma>0, Δ≥2\Delta\ge2, and k≥1k\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 p≥C∗n−2/(Δ+2)p\ge C^\ast n^{-2/(\Delta+2)}, every spanning subgraph GG of Γ\Gamma with

δ(G)≥(k−1k+γ)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 C∗p−2C^\ast p^{-2} vertices not contained in any triangles, and at least C∗p−(Δ+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}.

References

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.