4 papers · 1 filter
Monadic dependence from reducts, and applications to twin-width of oriented graphs
Hector Buffière, Yuquan Lin, Patrice Ossona de Mendez
We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a str…
On merge-models
Hector Buffière, Yuquan Lin, Jaroslav Nešet{ř}il +2
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 reconstruc…
Inversion diameter and 2-edge-colored homomorphisms
Carmen Arana, Thomas Bellitto, Hector Buffière +3
In an oriented graph, the inversion of a subset of vertices X is the operation reversing the direction of every arc with both endpoints in X. Given a graph G, the inversion distanc…
Characterizations of monadically dependent tree-ordered weakly sparse structures
Hector Buffière, Yuquan Lin, Jaroslav Nešetřil +2
A class of structures is monadically dependent if one cannot interpret all graphs in colored expansions from the class using a fixed first-order formula. A tree-ordered -structu…