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.
Abstract: We present a recent result that if a countable relational structure admits a stationary independence relation satisfying a few extra axioms, its automorphism group is simple (joint work with Evans, HubiÃÂka and Li). We then show how this relates to semigroup-valued metric spaces (joint work with HubiÃÂka and Neà ¡età Âil) and present some weak evidence that semigroup-valued metric spaces might be abundant among structures homogeneous in a binary symmetric language.
Abstract: Every better quasi-order codifies a Borel graph that does not contain a copy of the shift graph. It is known that there is a better quasi-order that codes a Borel graph with infinite Borel chromatic number, though one has yet to be explicitly constructed. In this paper, we show that examples cannot be constructed via standard methods. Moreover, we show that most of the known better quasi-orders are non-examples, suggesting there is still a class of better quasi-orders with interesting combinatorial properties who's elements/members still remain unknown.
Abstract: A classification of infinte primitive permutation Jordan group was given by Adeleke and Macpherson in 1995. On the class of limits, an example of an oligomorphic group such that its automorphisms preserves a limit of D-relations is found. This example is a structure M of trees of D-sets built by Fraisse construction. In this talk I will explain the example.
Abstract: I introduce trace definability, a weak notion of interpretability. This notion arose out of attempts to extend the Peterzil-Starchenko trichotomy to non o-minimal settings. Two theories are trace equivalent if each trace defines the other. Trace equivalence seems to be an interesting weak equivalence notion of theories, in particular for NIP theories. NIP-theoretic properties are preserved under trace definibility and there are non-trivial trace equivalences between NIP structures of interest. For example the theory of real closed fields is trace equivalent to the theory of real closed valued fields. It may also be possible, and interesting, to classify homogeneous structures up to trace definability, and this classification problem turns out to be closely related to indiscernible collapse.
Abstract: Pierre Simon introduced distality to better understand unstable NIP theories by studying their stable and ``purely unstable,'' or distal, parts separately. We introduce distality rank as a property of first-order theories and give examples for each rank $m$ such that $1\leq m \leq \omega$. For NIP theories, we show that distality rank is invariant under base change. We also define a generalization of type orthogonality called $m$-determinacy and show that theories of distality rank $m$ require certain products to be $m$-determined. Furthermore, for NIP theories, this behavior characterizes distality rank $m$. The preprint containing these results can be found at my website: https://homepages.math.uic.edu/~roland/. We will also discuss some new results not contained in the paper.
Abstract: Building on work of Lachlan, Greg Cherlin showed that, in principle, it is possible to classify permutation groups using homogeneous actions on finite relational structures. This classification has a number of rather attractive properties, most notably by its elimination of sporadic behaviour: all permutation group actions occur naturally in infinite families in a certain precise way. I will give a description of how this classification works, and then consider the problem of working out exactly where any given permutation group should fit in such a classification. To do this one needs to work out the RELATIONAL COMPLEXITY of a finite permutation group, a statistic that is easy to describe but rather tricky to calculate. The work I will describe in this talk has all been conducted in collaboration with Pablo Spiga as well as, at various times, Bianca Loda, Francesca Dalla Volta, Scott Hudson, Francis Hunt and Martin Liebeck.
Abstract: A theory is monadically NIP if it remains NIP after arbitrary expansions by unary predicates. This notion was initially studied by Baldwin and Shelah in the 1980s along with monadic stability, and further studied by Shelah soon afterwards. Expanding on that work, we give several characterizations of monadically NIP theories. These include a well-behaved independence notion, decomposability of models, forbidden configurations, and the behavior of indiscernibles. As a byproduct of the proof, we make partial progress towards a conjecture on the combinatorics of homogeneous structures. This is joint work with Chris Laskowski.
Abstract: In this talk first, we discuss the notion of asymptotic classes which was introduced by Macpherson and Steinhorn in 2008. Then we discuss some examples. Finally, as long as time permits, I will try to explain an idea of how to characterize N-dimensional asymptotic classes of finite trees (and their expansions). This is joint work (in progress) with Cameron Hill.
Abstract: In joint work with Richard Rast and Chris Laskowski, we introduced the notion of potential canonical Scott sentences; there and since, these objects have found numerous applications to the study of Borel complexity of first order theories (and generally, infinitary sentences). A disadvantage of these objects is that they are defined in terms of the forcing machinery, which significantly complicates their use. In this talk, we discuss a more direct model-theoretic treatment, and use it to recast and extend some old results of Hjorth. We also discuss some open problems. Joint work with Chris Laskowski.
Abstract: The field of infinite structural Ramsey theory is concerned with proving analogues of the classic infinite Ramsey's theorem to Fraisse limits. In most cases the exact analogue fails, but weaker versions having to do with certain bounds called big Ramsey degrees can be established. The work outlined in this talk defines a new type of amalgamation called Substructure Disjoint Amalgamation Property (SDAP) and uses it to establish for the first time finite big Ramsey degrees for certain structures. This is joint work with Natasha Dobrinen and Rehana Patel.
Abstract: Many problems arising in combinatorics and discrete geometry have solutions which involve functions F over N which are eventually quasi-polynomial: that is, there is some period m and polynomials f_1, ..., f_m such that for all sufficiently large t, F(t) = f_i(t) if and only if t is congruent to i (módulo m). The most well-known example is Ehrhart's Theorem: if P is a bounded polytope with rational vertices and F_P(t) is the number of points within the dilate tP of P with integer coordinates (where t ranges over positive integers), then F_P is quasi-polynomial. Other surprising examples of quasi-polynomial functions arise in parametric versions of the Frobenius problem (by work of Shen), the problem of finding the shortest nonzero vector in a lattice L = where a_i(t) is polynomial in t, and in computing Betti numbers of parametric families of numerical and affine semigroups.
Parametric Presbruger arithmetic (as developed by Bogart, G., and Woods) provides a unifying logical framework which connects many of these quasi-polynomial phenomena, as we will explain in the talk. Time permitting, we will also discuss some possible future directions for research on how to effectively bound the periodicity of quasi-polynomial functions and how parametric Presburger might be extended to incorporate other periodic behavior.