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.
Abstract: In the study of (finite) combinatorial structures equipped with a quasi ordering (for example, graphs with the induced subgraph ordering), the notion that a class of structures is âwell-quasi-orderedâ (wqo) equates to the absence of an infinite antichain in the class. Put another way, in a wqo class every infinite set of objects contains a pair, one of which precedes the other in the ordering. The combinatorial structure of choice for this talk is the permutation, equipped with the containment (=induced substructure) ordering. The notion of labeled well-quasi-order (commonly abbreviated to lwqo) is a significant strengthening of wqo, and dates back at least to Kruskalâs tree theorem in 1960, although it has received little attention in the realm of permutations before now. As the name suggests, it concerns combinatorial structures whose ground sets (for example, the vertices of a graph or the entries of a permutation) have been labeled by some ordered set L of labels, and considers the question of wqo on these labeled structures (under a refined ordering). In this talk, I will describe a recent programme to initiate the study of lwqo in the context of permutation classes. As well as being able to strengthen many earlier results about wqo to lwqo, it turns out that much more can be said about permutation classes that are lwqo over those that are simply wqo. Of particular note is that a permutation class is lwqo if and only if the corresponding class of permutation graphs is lwqo: the analogous statement for wqo remains open. This is based on joint work with Vince Vatter.
Abstract: We introduce the notion of K-rank, where K is an algebraically trivial Fraisse class, which measures the number of independent copies of K that can be coded into a partial type. This concept originated from the work of V. Guingona, C. Hill, and L. Scow, who used generalized indiscernibles to measure the complexity of theories. However, generalized indiscernibles are only guaranteed in Fraisse classes with the Ramsey property. In order to consider classes which don't have the Ramsey property, we introduce new notions of genericity for Fraisse classes that mimic certain aspects of the Ramsey property. These give us a sufficient amount of uniformity to allow us to count the number of independent copies of K that can be coded into a partial type. In this talk, I will define the notions of self-similar and weakly self-similar, give examples of Fraisse classes with these properties, and illustrate how they can be used to determine K-rank.