4 papers · 1 filter
Flip-packability: uniform characterisations of tame graph classes
Ioannis Eleftheriadis
A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot…
Extension preservation on dense graph classes
Ioannis Eleftheriadis
Preservation theorems provide a direct correspondence between the syntactic structure of first-order sentences and the closure properties of their respective classes of models. A l…
Preservation theorems on sparse classes revisited
Anuj Dawar, Ioannis Eleftheriadis
We revisit the work studying homomorphism preservation for first-order logic in sparse classes of structures initiated in [Atserias et al., JACM 2006] and [Dawar, JCSS 2010]. These…
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…