Some interactions between model theory and structural graph theory

30^th April 2024, 13:00 Ashton Lecture Theatre
Dr. Samuel Braunfeld
Charles University in Prague

Abstract

We will discuss how model-theoretic concepts concerned with separating tame from wild behavior in classes of infinite structures and with developing a structure theory for the tame classes can be applied to classes of finite structures, interacting with programs in structural graph theory. In particular, these concepts have been behind significant recent progress in determining when the general algorithmic problem of first-order model checking is (fixed-parameter) tractable.