Flipping and forking

Prelegent(ci)

Wojciech Przybyszewski

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

12 marca 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Flipping and forking

Seminarium

Seminarium „Teoria automatów”

---

In model theory, a model is called stable if it does not encode arbitrarily long linear orders using a single fixed formula, ensuring a form of combinatorial tameness. Stability is a central concept in Shelah’s classification program, which seeks to determine the number of non-isomorphic models of a given theory at each cardinality. A restricted notion of stability, called monadic stability, was introduced by Baldwin and Shelah in the 1980s and has recently emerged as a key concept in algorithmic graph theory and finite model theory. Many well-known graph classes are monadically stable; for example, interpretations of nowhere dense graph classes. Furthermore, it is one of the central notions in relation with the model checking problem for first-order logic: Dreier et al. [Arxiv:2311.18740] showed that model checking is fixed-parameter tractable for graph classes that are monadically stable.

One of the key features of stable theories developed by Shelah is that they admit a general notion of independence called non-forking independence, generalizing linear independence from vector spaces and algebraic independence from field theory. Although non-forking independence makes sense in arbitrary theories, and remains a key tool beyond stable theories, it has particularly good combinatorial properties in stable and monadically stable theories.

Since non-forking independence is defined purely in logical terms, a combinatorial characterization of this relation is sought. We prove that in the case of monadically stable graphs, non-forking independence can be characterized in terms of flip-independence. This is a combinatorial notion defined by Gajarský et al. [Arxiv:2301.13735]. It is based on the notion of a flip of a graph – edge complementation on an arbitrary subset of its vertices. Moreover, we extend the notions of flips, flip-independence, and their equivalence with non-forking independence to arbitrary monadically stable relational structures.

This is joint work with Szymon Toruńczyk.

---