3 papers
math.CO2025
Separability Properties of Monadically Dependent Graph Classes
Ãdouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis +5
A graph class is monadically dependent if one cannot interpret all graphs in colored graphs from using a fixed first-order interpretation. We prove that m…
cs.LO2024
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…
cs.LO2024
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…