2026-08-19T07:30:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22764 2025-10-02T11:31:22Z ddc:004 open_access

Extension Preservation on Dense Graph Classes Eleftheriadis, Ioannis Extension preservation finite model theory dense graphs cliquewidth 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 line of work has explored preservation theorems relativised to combinatorially tame classes of sparse structures [Atserias et al., JACM 2006; Atserias et al., SiCOMP 2008; Dawar, JCSS 2010; Dawar and Eleftheriadis, MFCS 2024]. In this article we initiate the study of preservation theorems for dense classes of graphs. In contrast to the sparse setting, we show that extension preservation fails on most natural dense classes of low complexity. Nonetheless, we isolate a technical condition which is sufficient for extension preservation to hold, providing a dense analogue to a result of [Atserias et al., SiCOMP 2008]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Eleftheriadis 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.7 urn:nbn:de:0030-drops-227640 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.7 eng https://creativecommons.org/licenses/by/4.0/legalcode