Abstract: The \emph{Constraint Satisfaction Problem} (CSP) over a structure $\mathfrak{A}$ with a finite relational signature is the problem of deciding whether a given finite structure $\mathfrak{B}$ with the same signature as $\mathfrak{A}$ has a homomorphism to $\mathfrak{A}$. Using concepts and techniques from universal algebra, Bulatov and Zhuk proved that if $\mathfrak{A}$ is finite, then the CSP over $\mathfrak{A}$ is always in $\mathbf{P}$ or $\mathbf{NP}$-complete. Following this result, it is a natural question to ask when and how this dichotomy can be generalized for infinite structures. The infinite domain CSP dichotomy conjecture (originally formulated by Bodirsky and Pinsker) states that the same complexity dichotomy holds for first-order reducts of finitely bounded homogeneous structures. In this talk I will talk about how this conjecture can be proved for the class of monadically stable structures, as well as giving an introduction to the notion of monadic stability.
A structure $\mathfrak{A}$ is called \emph{monadically stable} iff every expansion of $\mathfrak{A}$ by unary predicates is stable. Despite the innocent look it turns out that this condition is very restrictive. In fact we can describe the class $\mathcal{M}$ of monadically stable structures as follows: $\mathcal{M}$ is the smallest class of structures which contains all finite structures, and is closed under taking finite disjoint unions, infinite copies, and first-order reducts. In this talk I will also present some other ways to describe the class $\mathcal{M}$, and show some interesting consequences of monadic stability.
Abstract: By studying the Borel complexity of countable families of cross-cutting equivalence relations, we are able to prove that (1) if T has uncountably many 1-types, then T has a Borel complete reduct; (2) if T is not small, then Teq has a Borel complete reduct; and (3) if T is not omega-stable, then the elementary diagram of any model of T has a Borel complete reduct. We also show that `not all Borel complete theories are equally complicated' by mentioning a stronger notion that holds of some Borel complete theories but not others. This is joint work with Douglas Ulrich.
4176 Campus Drive - William E. Kirwan Hall
College Park, MD 20742-4015
P: 301.405.5047 | F: 301.314.0827