The dense analogue characterization conjecture for merge-width and flip-width

Let C\mathcal C be a graph class. Following the paper, say that C\mathcal C is in the dense analogue of bounded expansion if, for every weakly sparse graph class D\mathcal D such that C\mathcal C transduces D\mathcal D, the class D\mathcal D has bounded expansion. Dense analogue characterization conjecture. The following conditions are equivalent:

(i)C has bounded merge-width,(ii)C has bounded flip-width,(iii)C is in the dense analogue of bounded expansion.\begin{array}{ll} \text{(i)} & \mathcal C\text{ has bounded merge-width},\\ \text{(ii)} & \mathcal C\text{ has bounded flip-width},\\ \text{(iii)} & \mathcal C\text{ is in the dense analogue of bounded expansion}. \end{array}

The conjecture would provide an obstruction-based characterization of bounded merge-width and bounded flip-width. It is known in the paper for graph classes excluding a biclique as a subgraph and for classes of ordered graphs, while the general equivalence 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.