Preservation theorems on tame classes of finite structures

Speaker(s)

Ioannis Eleftheriadis

Affiliation

University of Cambridge

Language of the talk

English

Date

Oct. 2, 2024, 2:15 p.m.

Room

room 5070

Title in Polish

Preservation theorems on tame classes of finite structures

Seminar

Seminar Automata Theory

---

Preservation theorems provide a correspondence between the syntactic structure and the semantic behaviour of first-order sentences. The study of preservation theorems relativised to classes of finite structures was initiated by Atserias, Dawar, and Kolaitis [JACM, 2006] who established that any almost-wide class closed under substructures and disjoint unions has the so-called homomorphism preservation property. In this talk we will revisit the above line of work and argue that the status of preservation theorems is more subtle than previously believed. Strikingly, we shall construct a counter example to the claim of Atserias et al and prove a weaker version of their result. Time permitting, we will discuss some recent attempts to lift these results to the context of dense graph classes.

---