The almost bounded merge-width characterization conjecture

Let C\mathcal C be a hereditary graph class. It has almost bounded merge-width if, for each fixed rNr\in\mathbb N, every nn-vertex graph in C\mathcal C has radius-rr merge-width at most no(1)n^{o(1)}; analogously define almost bounded flip-width by replacing merge-width with flip-width. The class C\mathcal C is monadically dependent if and only if it does not transduce the class of all graphs. Almost bounded merge-width characterization conjecture. The following conditions are equivalent:

(i)C has almost bounded merge-width,(ii)C has almost bounded flip-width,(iii)C is monadically dependent.\begin{array}{ll} \text{(i)} & \mathcal C\text{ has almost bounded merge-width},\\ \text{(ii)} & \mathcal C\text{ has almost bounded flip-width},\\ \text{(iii)} & \mathcal C\text{ is monadically dependent}. \end{array}

For hereditary weakly sparse classes, the first two conditions are equivalent to nowhere denseness, and nowhere dense classes have almost bounded merge-width. The general hereditary characterization by monadic dependence remains open.

Sources & referencesView supporting material

Primary source

Jan Dreier and Szymon Toruńczyk, “Merge-width and First-Order Model Checking”, arXiv:2502.18065 (2026).

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.