Optimal sparse blow-up conjecture for bounded-bandwidth graphs
Optimal sparse blow-up conjecture for bounded-bandwidth graphs
For each , , and , there should exist constants and such that, asymptotically almost surely for whenever , every spanning subgraph of with
and every -colourable graph on vertices with , bandwidth at most , at least vertices not contained in any triangles, and at least vertices not contained in any , satisfy the following. Sparse blow-up conjecture. The graph contains a copy of . This conjecture proposes the expected optimal lower bound on , accounting for the necessary obstructions caused by vertices of outside triangles and copies of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.