Merge-width characterised by FO-transduction neighbourhood complexity

Status open high confidence

The source paper itself establishes the left-to-right direction (Theorem 1.5): every first-order transduction of a bounded merge-width class has linear neighbourhood complexity. The converse—that linear neighbourhood complexity of all first-order transductions implies bounded merge-width—remains open as of early 2026. A February 2026 follow-up (arXiv:2602.12926) makes related partial progress by showing that in K_{t,t}-free graphs flip-width coincides with bounded expansion and with bounded merge-width, which is relevant to the flip-width/merge-width equivalence conjecture (implied by Conjecture 1.7) but does not address the neighbourhood-complexity characterisation directly.

Cited literature (1)

• partial Flips and Merge-Width in Sparse Graphs (2026)
  Karolina Drabik, Maël Dumas, Nikolas Mählmann, Wojciech Przybyszewski, Szymon Toruńczyk · arXiv preprint · arXiv:2602.12926

  In K_{t,t}-free graphs, shows that every short sequence of flips can be simulated by vertex deletions, and derives that flip-width, bounded expansion, and bounded merge-width all coincide in the sparse setting; this constitutes partial progress toward the merge-width/flip-width equivalence conjecture implied by Conjecture 1.7 but does not resolve the neighbourhood-complexity characterisation.

Reviewer notes. The left-to-right direction of Conjecture 1.7 is already proven in the source paper (Theorem 1.5). The conjecture is stated as open and, if resolved, would also imply the equivalence of flip-width and merge-width (Dreier–Toruńczyk Conjecture 1.17 in arXiv:2502.18065). No paper directly resolving the full conjecture was found after 5 web calls.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).