Preservation theorems on tame classes of finite structures

Prelegent(ci)

Ioannis Eleftheriadis

Afiliacja

University of Cambridge

Język referatu

angielski

Termin

2 października 2024 14:15

Pokój

p. 5070

Tytuł w języku polskim

Preservation theorems on tame classes of finite structures

Seminarium

Seminarium „Teoria automatów”

---

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.

---