6 papers
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 -struct…
Decomposing graphs into stable and ordered parts
Hector Buffière, Patrice Ossona de Mendez
Connections between structural graph theory and finite model theory recently gained a lot of attention. In this setting, many interesting questions remain on the properties of depe…
Blind cop-width and balanced minors of graphs
Hector Buffière, Rutger Campbell, Kevin Hendrey +1
We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's loc…