Logic Archives for Fall 2021 to Spring 2022
CSP dichotomy for monadically stable structures
When: Fri, October 16, 2020 - 2:05pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Bertalan Bodor (TU Dresden) -
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.
Most(?) theories have Borel complete reducts
When: Thu, October 29, 2020 - 2:05pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Chris Laskowski (UMD, College Park) -
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.
Labeled well-quasi-order for permutation classes
When: Thu, November 5, 2020 - 12:00pmWhere: https://www.google.com/url?q=https%3A%2F%2Fumd.zoom.us%2Fj%2F94409708118%3Fpwd%3DN0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09&sa=D&ust=1604501005492000&usg=AOvVaw28r5nmXqRiUQMnpU6_6VX5
Speaker: Robert Brignall (The Open University) -
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.
High and low formulas in modules
When: Fri, November 13, 2020 - 2:05pmWhere: Online
Speaker: Philipp Rothmaller (CUNY) -
Coding Fraisse Classes`
When: Thu, November 19, 2020 - 12:00pmWhere: https://www.google.com/url?q=https%3A%2F%2Fumd.zoom.us%2Fj%2F94409708118%3Fpwd%3DN0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09&sa=D&ust=1605649916633000&usg=AOvVaw23hiY9XEptmO-r3RiY-IRo
Speaker: Miriam Parnes (Towson University) -
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.
This work is joint with Vince Guingona.
Classification of oligomorphic groups with polynomial profiles, conjectures of Cameron and Macpherson.
When: Fri, December 4, 2020 - 2:00pmWhere: https://www.google.com/url?q=https%3A%2F%2Fumd.zoom.us%2Fj%2F94409708118%3Fpwd%3DN0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09&sa=D&ust=1607028668631000&usg=AOvVaw133S-W5nUZpT2xK8LYXmv_
Speaker: Justine Falque (Université Paris-Sud) -
Abstract: Let G be a group of permutations of a denumerable set E. The profile
of G is the function f which counts, for each n, the (possibly
infinite) number f(n) of orbits of G acting on the n-subsets of E.
When f takes only finite values, G is called oligomorphic.
Counting functions arising this way, and their associated generating
series, form a rich yet apparently strongly constrained class. In
particular, Cameron conjectured in the late seventies that, whenever
the profile f(n) is bounded by a polynomial (we say that G is
P-oligomorphic), it is asymptotically equivalent to a polynomial. In
1985, Macpherson further asked whether the orbit algebra of G (a
graded commutative algebra invented by Cameron and whose Hilbert
function is f) was finitely generated.
After providing some context and definitions of the involved objects,
this talk will outline the proof of a classification result of all
(closed) P-oligomorphic groups, of which the conjectures of Cameron and
Macpherson are corollaries.
The proof exploits classical notions from group theory (notably
block systems and their lattice properties), commutative algebra,
and invariant theory. This research was a joint work with
Nicolas Thiéry.
On homogeneous structures in a binary symmetric language
When: Thu, February 4, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Matěj Konečný (Charles University) -
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.
Borel Colouring Bad Sequences
When: Thu, February 11, 2021 - 3:30pmWhere: https://www.google.com/url?q=https%3A%2F%2Fumd.zoom.us%2Fj%2F94409708118%3Fpwd%3DN0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09&sa=D&ust=1612752528723000&usg=AOvVaw2dgPNNfkBpRFGMvq55f3T7
Speaker: Keegan Dasilva Barbosa (University of Toronto) -
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.
Jordan Permutation Groups and limits of D-relations
When: Thu, February 18, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Asma Mazaydeh (Tafila Technical University) -
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.
Trace definability
When: Thu, February 25, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Erik Walsberg (UC Irvine) -
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.
Distality Rank
When: Thu, March 4, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Roland Walker (University of Illinois, Chicago) -
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.
What generic automorphisms of the random poset look like
When: Thu, March 11, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Dakota Thor Ihli (University of Illinois, Urbana-Champaign) -
Abstract: The random poset, the Fraïssé limit of the class of finite posets, admits generic automorphisms — that is, its automorphism group admits a comeagre conjugacy class. This result, due to D. Kuske and J. Truss, was proven without explicitly describing the automorphisms in question. Here we give a new, concrete description of the generic automorphisms, and we discuss the combinatorics and model theory involved.
Using model theory to "classify" finite permutation groups
When: Thu, March 25, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Nick Gill (University of South Wales) -
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.
Characterizations of monadic NIP
When: Thu, April 8, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Samuel Braunfeld (University of Maryland, College Park) -
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.
Asymptotic classes of finite trees
When: Thu, April 15, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Mostafa Mirabi (Wesleyan University) -
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.
A Model-Theoretic Approach to Potential Canonical Scott Sentences
When: Thu, April 22, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Douglas Ulrich () -
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.
Fraisse classes with simply characterized big Ramsey degrees via amalgamation
When: Thu, April 29, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Rebecca Coulson (US Military Academy) -
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.
Explaining periodic behavior with parametric Presburger arithmetic
When: Thu, May 6, 2021 - 3:30pmWhere: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: John Goodrick (Universidad de los Andes) -
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.
Flows on sparse graphs
When: Thu, May 13, 2021 - 3:30pmWhere: Where: https://umd.zoom.us/j/94409708118?pwd=N0k2dkt0NmpGaGhyRVVnTnM2RW5kdz09
Speaker: Robert Sullivan (Imperial College London) -
Abstract: The KPT correspondence established a link between topological dynamics (extreme amenability) and Ramsey theory, which was later extended by work of Nguyen Van Thé, Tsankov, Melleray and Zucker. In this talk we will examine some flows on sparse graphs in this context: specifically, we will consider orientations and linear orders on Hrushovski constructions, discussing their dynamical properties from a Ramsey theory perspective. We will discuss some results proved by the speaker and David Evans, continuing work of Evans, Hubička and Nešetřil.