Logic Archives for Fall 2024 to Spring 2025
Organizational meeting
When: Tue, August 29, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Organizational Meeting () -
Ergodic theorems along trees
When: Tue, September 5, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Jenna Zomback (University of Maryland, College Park) -
Abstract: In the classical pointwise ergodic theorem for a probability measure preserving (pmp) transformation T, one takes averages of a given integrable function over the intervals ($x$, $Tx$, $T^2 x$,...,$T^n x$) in front of the point $x$. We prove a “backward” ergodic theorem for a countable-to-one pmp $T$, where the averages are taken over subtrees of the graph of $T$ that are rooted at $x$ and lie behind $x$ (in the direction of $T^{-1}$). Surprisingly, this theorem yields (forward) ergodic theorems for countable groups, in particular, ones for pmp actions of free groups and semigroups of finite rank. In each case, the averages are taken along subtrees of the standard Cayley graph rooted at the identity. This is joint work with Anush Tserunyan.
How Computable is Ramsey's Theorem?
When: Tue, September 12, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: William Gasarch (University of Maryland, College Park) -
Abstract: Recall Ramsey's Theorem:
For all 2-colorings of unordered pairs of naturals there exists an infinite homogeneous set
(a set H such that all pairs from H are the same color).
If the coloring is computable then will the homogenous set be computable?
We show NO (a result due to Spector).
So what can we say about the complexity of H in the arithmetic hierarchy?
Come and find out!
Indivisibility and strong substructures
When: Tue, September 19, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Vincent Guingona (Towson University) -
Abstract: In this talk, I will discuss some of the work that Miriam Parnes and I did with four undergraduate students at an REU over the summer. This work was motivated by earlier work of myself and various other authors (Cameron Hill, Miriam Parnes, and Lynn Scow) investigating configurations as a means of classifying theories. We discovered that imposing some level of uniformity on the index class aided in understanding configurations and, while the Ramsey property was too restrictive, indivisibility seemed be sufficient. This talk will focus on indivisibility, especially viewed through the lens of classes of structures with a notion of strong substructure. (This work is joint with Felix Nusbaum, Zain Padamsee, Miriam Parnes, Christian Pippin, and Ava Zinman.)
Indivisibility for Classes of Graphs
When: Tue, September 26, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Miriam Parnes (Towson University) -
Abstract: In this talk, we will discuss the results of the 2023 Towson University REU on indivisibility of classes of finite graphs. We will first consider indivisibility for hereditarily sparse graphs. Then we will turn our attention to a number of classes of graphs which are characterized by forbidden induced subgraphs, including cographs and perfect graphs. This is joint work with Vince Guingona, Felix Nusbaum, Zain Padamsee, Christian Pippin, and Ava Zinman.
Regularity lemma for slice-wise stable hypergraphs
When: Tue, October 3, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Artem Chernikov (University of Maryland) -
Abstract: We will discuss various strengthenings of Szemerédi's regularity lemma for hypergraphs that are tame from the model-theoretic point of view.
Generalizing the case of stable graphs due to Malliaris and Shelah, we have shown the following in a joint work with Starchenko: if a 3-hypergraph E(x,y,z) on X x Y x Z is stable when viewed as a binary relation under any partition of its variables in two groups, then there are partitions X_i of X, Y_j or Y and Z_k of Z so that the density of E on any box X_i x Y_j x Z_k is either 0 or 1.
Terry and Wolf raised the question if the assumption can be relaxed to slice-wise stability, i.e. for any z in Z, the corresponding fiber E_z is a stable relation on X x Y, and similarly for any permutation of the variables (analogous slice-wise assumption is known to be correct in the NIP case).
We provide an example of a slice-wise stable 3-hypergraph which does not satisfy the stable regularity lemma above, and establish an optimal weaker partition result for slice-wise stable hypergraphs. Joint work with Henry Towsner.
Regularity lemma for slice-wise stable hypergraphs, Part 2
When: Tue, October 10, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Artem Chernikov (University of Maryland) -
Abstract: We will discuss various strengthenings of Szemerédi's regularity lemma for hypergraphs that are tame from the model-theoretic point of view.
Generalizing the case of stable graphs due to Malliaris and Shelah, we have shown the following in a joint work with Starchenko: if a 3-hypergraph E(x,y,z) on X x Y x Z is stable when viewed as a binary relation under any partition of its variables in two groups, then there are partitions X_i of X, Y_j or Y and Z_k of Z so that the density of E on any box X_i x Y_j x Z_k is either 0 or 1.
Terry and Wolf raised the question if the assumption can be relaxed to slice-wise stability, i.e. for any z in Z, the corresponding fiber E_z is a stable relation on X x Y, and similarly for any permutation of the variables (analogous slice-wise assumption is known to be correct in the NIP case).
We provide an example of a slice-wise stable 3-hypergraph which does not satisfy the stable regularity lemma above, and establish an optimal weaker partition result for slice-wise stable hypergraphs. Joint work with Henry Towsner.
Regularity lemma for slice-wise stable hypergraphs, Part 3
When: Tue, October 17, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Artem Chernikov (University of Maryland) -
Abstract: We will discuss various strengthenings of Szemerédi's regularity lemma for hypergraphs that are tame from the model-theoretic point of view.
Generalizing the case of stable graphs due to Malliaris and Shelah, we have shown the following in a joint work with Starchenko: if a 3-hypergraph E(x,y,z) on X x Y x Z is stable when viewed as a binary relation under any partition of its variables in two groups, then there are partitions X_i of X, Y_j or Y and Z_k of Z so that the density of E on any box X_i x Y_j x Z_k is either 0 or 1.
Terry and Wolf raised the question if the assumption can be relaxed to slice-wise stability, i.e. for any z in Z, the corresponding fiber E_z is a stable relation on X x Y, and similarly for any permutation of the variables (analogous slice-wise assumption is known to be correct in the NIP case).
We provide an example of a slice-wise stable 3-hypergraph which does not satisfy the stable regularity lemma above, and establish an optimal weaker partition result for slice-wise stable hypergraphs. Joint work with Henry Towsner.
Forcing with model-theoretic trees
When: Tue, October 24, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: James Hanson (University of Maryland) -
Abstract: We will discuss a characterization of first-order theories realizing a certain combinatorial tree configuration in terms of special coheirs. One direction of the proof can be understood as a kind of forcing argument.
Dynamics of the Knaster continuum homeomorphism group
When: Tue, October 31, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Sumun Iyer (Cornell University) -
Abstract: Knaster continua are a class of compact, connected, metrizable spaces which are indecomposable in the sense that they cannot be written as the union of two proper non-trivial subcontinua. Let $K$ be the universal Knaster continuum (this is a unique Knaster continuum which continuously and openly surjects onto all other Knaster continua). The group $\textrm{Homeo}(K)$ of all homeomorphisms of the universal Knaster continuum is a non-locally compact Polish group. We prove that it contains an open subgroup which exhibits two ``large Polish group'' phenomena: the existence of a comeager conjugacy class and extreme amenability.
On some problems regarding bases in Banach spaces and lattices
When: Tue, November 7, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Christian Rosendal (University of Maryland) -
Abstract: The concept of a Schauder basis is central to Banach space theory, but occasionally too wide to be useful in Banach lattices, while too restrictive for general separable Banach spaces. In Banach lattices, new notions of bases incorporate different types of order convergence, whereas in Banach space, one can conversely weaken sequential convergence to filter convergence. Applying tools from descriptive set theory, we answer several fundamental questions due to Gumenchuk, Karlova and Popov (J. Funct. Anal. 2015), Taylor and Troitsky (J. Funct. Anal. 2020), and de Rancourt, Kania and Swaczyna (J. Funct. Anal. 2023) related to these concepts. This is a joint work with A. Àviles, M. A. Taylor and P. Tradacete.
On some problems regarding bases in Banach spaces and lattices (Part 2)
When: Tue, November 14, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Christian Rosendal (University of Maryland) -
Abstract: The concept of a Schauder basis is central to Banach space theory, but occasionally too wide to be useful in Banach lattices, while too restrictive for general separable Banach spaces. In Banach lattices, new notions of bases incorporate different types of order convergence, whereas in Banach space, one can conversely weaken sequential convergence to filter convergence. Applying tools from descriptive set theory, we answer several fundamental questions due to Gumenchuk, Karlova and Popov (J. Funct. Anal. 2015), Taylor and Troitsky (J. Funct. Anal. 2020), and de Rancourt, Kania and Swaczyna (J. Funct. Anal. 2023) related to these concepts. This is a joint work with A. Àviles, M. A. Taylor and P. Tradacete.
Towards Erdős-Hajnal property for dp-minimal graphs
When: Tue, November 21, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Yayi Fu (University of Notre Dame) -
Abstract: Abstract: We introduce the notion of strongly $\binom{k}{2}$-free graphs, which contain dp-minimal graphs. We show that under some sparsity assumption, given a rainbow $\binom{k}{2}$-free blockade we can find a rainbow $\binom{k-1}{2}$-free blockade. This might serve as an intermediate step towards Erdős-Hajnal property for dp-minimal graphs.
Characterizing Hard Tautologies
When: Tue, November 28, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Hunter Monroe () -
Abstract: Consider the following question: does the partial order over theories
Higher arity stability and the functional order property
When: Tue, December 5, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Gabriel Conant (Ohio State University) -
Abstract: I will discuss recent work with Abd Aldaim and Terry on the model theory of a new notion of stability formulated for a (k+1)-partitioned formula (with classical stability corresponding to the k=1 case). The focus will be on basic properties, fundamental examples, and further open questions.
Dynamical obstructions to classification by (co)homology and other TSI invariants
When: Tue, December 12, 2023 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Aristotelis Panagiotopoulos (Carnegie Mellon University) -
Abstract: One of the leading questions in many mathematical research programs is whether a certain classification problem admits a “satisfactory” solution. As it turns out, however, some classification problems are intrinsically too complex to admit complete classification by "simple" invariants. Hjorth's theory of turbulence, for example, provides conditions under which a classification problem cannot be solved using isomorphism types of countable structures as invariants. In this talk we will introduce "unbalancedness": a new dynamical obstruction to classification by orbits of Polish groups which admit a two-side invariant metric (TSI). We will illustrate how "unbalancedness" can be used for showing that a classification problem cannot be solved by classical homology and cohomology invariants and discuss applications. This is joint work with Shaun Allison.
Distality in Continuous Logic
When: Tue, January 30, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Aaron Anderson (UCLA) -
Abstract: We examine distal theories and structures in the context of continuous logic, providing several equivalent definitions.
By studying the combinatorics of fuzzy VC-classes, we find continuous versions of (strong) honest definitions and distal cell decompositions.
By studying generically stable Keisler measures in continuous logic, we apply the theory of continuous distality to analytic versions of graph regularity.
We will also present some examples of distal metric structures, including dual linear continua and a continuous version of o-minimality.
Minimality of the compact-open topology on homeomorphism and diffeomorphism groups of manifolds
When: Tue, February 13, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Javier de la Nuez González (Korea Institute for Advanced Study) -
Abstract: We discuss recent work in which we prove that in almost all dimensions the compact open topology on the diffeomorphism or homeomorphism group of a smooth manifold is minimal, i.e. the group does not admit a strictly coarser Hausdorff group topology. When combined with automatic continuity results in the literature, this yields a strong form of topological rigidity for the homeomorphism group of many manifolds.
Complex Polynomials up to Interdefinability
When: Tue, February 20, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Benjamin Castle (University of Maryland, College Park) -
Abstract: Motivated by the recent solution of Zilber's Restricted Trichotomy Conjecture, we study reducts of the complex field up to interdefinability over parameters. Precisely, we will consider structures of the form $(\mathbb C, P_1,...,P_n)$, where the $P_i$ are polynomial maps of potentially different arities. Somewhat surprisingly, our main result states that almost all such structures (in a precise sense) are interdefinable. The proof uses a mix of tools from geometric stability theory, combinatorics, and algebraic geometry. This is joint work with Chieu-Minh Tran.
Around affine logic
When: Tue, February 27, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Itaï Ben Yaacov (Institut Camille Jordan) -
Abstract: Joint work with Tomás Ibarlucía and Todor Tsankov
Affine logic, originally introduced by Bagheri as « linear logic », is a real-valued logic in which we only allow affine functions as connectives (compared with continuous logic, in which all continuous connectives are allowed). In an ongoing work with Ibalucía and Tsankov we explore this logic and its semantics, with emphasis on the special role of extreme types (namely, extreme points in the compact convex sets of types). Many natural classes of structures admit affine axiomatisations, one of which being the Keisler randomisations of a fixed continuous (or classical) theory.
Some results on dp-minimal groups
When: Tue, March 5, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Atticus Stonestorm () -
Abstract: Dp-minimality is a kind of abstract model-theoretic "one-dimensionality" condition, satisfied for example by superstable theories of U-rank 1 and o-minimal theories. In this talk we will introduce dp-minimality, and then discuss some results on dp-minimal groups: namely, every torsion-free dp-minimal group is abelian, and every distal dp-minimal group is nilpotent-by-finite.
Pushing Properties for NIP Groups and Fields up the n-dependent hierarchy
When: Tue, March 12, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Nadja Hempel (Heinrich-Heine-Universität Düsseldorf) -
Abstract: (joint with Chernikov)
1-dependent theories, better known as NIP theories, are the first class of the strict hierarchy of n-dependent theories. The random n-hypergraph is one canonical object which is n-dependent but not (n−1)-dependent. We proved the existence of strictly n-dependent groups for all natural numbers n. On the other hand, there are no known examples of strictly n-dependent fields and we conjecture that there aren’t any.
We were interested which properties of groups and fields for NIP theories remain true in or can be generalized to the n-dependent context. A crucial fact about (type-)definable groups in NIP theories is the absoluteness of their connected components. Our first aim is to give examples of n-dependent groups and discuss a adapted version of absoluteness of the connected component. Secondly, we will review the known properties of NIP fields and see how they can be generalized.
Erdős–Hajnal and VC-dimension
When: Tue, April 2, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Tung Nguyen (Tung Nguyen) -
Abstract: A hereditary class $\mathcal C$ of graphs is said to have the Erdős–Hajnal property if every $n$-vertex graph in $\mathcal C$ has a clique or stable set of size at least $n^c$. We discuss a proof of a conjecture of Chernikov–Starchenko–Thomas and Fox–Pach–Suk that for every $d\ge1$, the class of graphs of VC-dimension at most $d$ has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.
Trees, countable Borel equivalence relations and median graphs
When: Tue, April 9, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Ran Tao (Carnegie Mellon University) -
Abstract: We will explore an application of median graphs and dual objects to the problem of treeability of quasi-treeable countable Borel equivalence relations in descriptive set theory. Median graphs and their duals are well-studied objects, in particular in geometric group theory. This is joint work with Ruiyuan Chen, Antoine Poulin and Anush Tserunyan.
Asymptotics of the Spencer-Shelah Random Graph Sequence
When: Tue, April 16, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Alex Van Abel (Wesleyan University) -
Abstract: In combinatorics, the Spencer-Shelah random graph sequence is a variation on the independent-edge random graph model. We fix an irrational number $a \in (0,1)$, and we probabilistically generate the n-th Spencer-Shelah graph (with parameter $a$) by taking $n$ vertices, and for every pair of distinct vertices, deciding whether they are connected with a biased coin flip, with success probability $n^{-a}$. On the other hand, in model theory, an $R$-mac is a class of finite structures, where the cardinalities of definable subsets are particularly well-behaved. In this talk, we will introduce the notion of "probabalistic $R$-mac" and sketch the proof that the Spencer Shelah random graph sequence is an example of one.
Combinatorics of banned sequences
When: Tue, April 23, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Alexei Kolesnikov (Towson University) -
Abstract: It is well known that for a formula $\varphi$ one of the following is true: either there are arbitrarily large finite sets $A$ such that the number of consistent $\varphi$-types over $A$ is $2^{|A|}$ or the number of consistent $\varphi$-types over any finite set $A$ is bounded by a polynomial in the size of $A$. Bhaskar showed that a similar dichotomy is true when we count the number of consistent types over trees of parameters: the number of consistent $\varphi$-types is either exponential or bounded by a polynomial in the depth of the tree. Chase and Freitag found a unified way to explain the upper bounds on the number of consistent types in both cases by counting what they called banned sequences. In this talk, I will present a simplified argument for counting banned sequences and will discuss possible extensions. This is joint work with Vince Guingona.
Limits of sparse structures
When: Tue, April 30, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Riley Thornton (Carnegie Mellon University) -
Abstract: Local-global limits let one transfer results from measurable combinatorics to asymptotic results about sequences of graphs. Folklore has it that local-global limits of graphs capture the same information as weak equivalence classes of pmp actions and (continuous) existential theories of probability algebras with automorphisms. I'll try to explain some of these connections and report on recent work generalizing local-global limits to hypergraphs and other structures.
Complexity of codes for Ramsey positive sets
When: Tue, May 7, 2024 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Allison Wang (Carnegie Mellon University) -
Abstract: A subset $X$ of the Ellentuck space is called Ramsey null if given any non-empty basic open set $[s, A]$, there is $B \in [s, A]$ such that $[s, B]$ and $X$ are disjoint. A set is Ramsey positive if it is not Ramsey null. Sabok proved that in Ellentuck space, the set of codes for $G_\delta$ Ramsey positive sets is $\Sigma^1_2$-complete. We build on Sabok's result to show that the same holds in the Milliken space of strong subtrees of the complete binary tree. In fact, we will see that the result holds for any topological Ramsey space satisfying a certain condition, including many common Ramsey spaces.