On merge-models
This work provides a theoretical framework for structural graph theory, offering incremental advancements in model representation for structures with bounded width parameters.
The paper tackles the problem of representing binary relational structures with bounded twin-width using tree-ordered weakly sparse models, showing that merge-models generalize twin-models and preserve properties like linear clique-width up to a constant factor.
Tree-ordered weakly sparse models have recently emerged as a robust framework for representing structures in an ``almost sparse'' way, while allowing the structure to be reconstructed through a simple first-order interpretation. A prominent example is given by twin-models, which are bounded twin-width tree-ordered weakly sparse representations of structures with bounded twin-width derived from contraction sequences. In this paper, we develop this perspective further. First, we show that twin-models can be chosen such that they preserve linear clique-width or clique-width up to a constant factor. Then, we introduce \emph{merge-models}, a natural analog of twin-models for merge-width. Merge-models represent binary relational structures by tree-ordered weakly sparse structures. The original structures can then be recovered by a fixed first-order interpretation. A merge-model can be constructed from a merge sequence. Then, its radius-$r$ merge-width will be, up to a constant factor, bounded by the radius-$r$ width of the merge sequence from which it is derived. Finally, we show that twin-models arise naturally as special cases of merge-models, and that binary structures with bounded twin-width are exactly those having a loopless merge-model with bounded radius-$r_0$ merge-width (for some sufficiently large constant $r_0$).