Extension preservation on dense graph classes

2024/08/05 by Ioannis Eleftheriadis, Eleftheriadis, Ioannis · 1 citation
Computer Science · #Constraint Satisfaction and Optimization #Advanced Graph Theory Research #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2408.02388

Abstract

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, 2024]. In this article we initiate the study of preservation theorems for dense graph classes. 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].

Cited by

• Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide

Related

• Preservation theorems on sparse classes revisited
• A Generalization of the Łoś-Tarski Preservation Theorem - Dissertation Summary
• When Locality Meets Preservation
• Nowhere dense graph classes and algorithmic applications. A tutorial at\n Highlights of Logic, Games and Automata 2019
• First-order interpretations of bounded expansion classes