2026-07-23T20:32:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20603 2024-08-23T05:50:29Z ddc:004 open_access

Preservation Theorems on Sparse Classes Revisited Dawar, Anuj Eleftheriadis, Ioannis Homomorphism preservation sparsity finite model theory planar graphs 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 established that first-order logic has the homomorphism preservation property in any sparse class that is monotone and addable. It turns out that the assumption of addability is not strong enough for the proofs given. We demonstrate this by constructing classes of graphs of bounded treewidth which are monotone and addable but fail to have homomorphism preservation. We also show that homomorphism preservation fails on the class of planar graphs. On the other hand, the proofs of homomorphism preservation can be recovered by replacing addability by a stronger condition of amalgamation over bottlenecks. This is analogous to a similar condition formulated for extension preservation in [Atserias et al., SiCOMP 2008]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Ioannis Eleftheriadis 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.47 urn:nbn:de:0030-drops-206036 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.47 eng https://creativecommons.org/licenses/by/4.0/legalcode