The dense analogue characterization conjecture for merge-width and flip-width
The dense analogue characterization conjecture for merge-width and flip-width
Let be a graph class. Following the paper, say that is in the dense analogue of bounded expansion if, for every weakly sparse graph class such that transduces , the class has bounded expansion. Dense analogue characterization conjecture. The following conditions are equivalent:
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
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.