We introduce a “purely Borel” version of Gromov’s notion of asymptotic dimension, and show how to use it to establish hyperfiniteness of various equivalence relations. Time permitting, we discuss hyperfiniteness of orbit equivalence relations of free actions of lamplighter groups. This is joint work with Jackson, Marks, Seward, and Tucker-Drob.
Let \(\Gamma\) be a countable free group. The set of continuous actions of \(\Gamma\) on Cantor space \(2^\mathbb{N}\) admits a natural Polish topology, and hence we can talk about properties of the generic action. It was shown by Frisch-Kechris-Shinko-Vidnyánszky that the generic action is measure-hyperfinite, meaning that for every Borel probability measure \(\mu\) on \(2^{\mathbb{N}}\), the action is hyperfinite modulo some \(\mu\)-null set. Kwiatkowska showed using the methods of projective Fraïssé theory that there is only one generic action up to isomorphism. We use her techniques to investigate the generic action further, and in particular we show that the generic action is hyperfinite. This is joint work with Sumun Iyer.
One difficulty that arises in studying the class of countable Borel equivalence relations (CBERs) is that in many cases, the complexity of a CBER lies on a "small" set. For instance, a result of Hjorth and Kechris states that every CBER on a Polish space is hyperfinite when restricted to some comeager set. Another result, due to Mathias, shows that every CBER on the Ellentuck Ramsey space is hyperfinite when restricted to some pure Ellentuck cube. In this talk, we will show that every CBER on the space of all infinite partitions of the natural numbers coincides with equality below a Carlson-Simpson generic element. This is joint work with Aristotelis Panagiotopoulos.
Vizing's theorem asserts that every graph of degree bounded by \(\Delta<+\infty\) admits a proper edge coloring with \((\Delta+1)\) colors. I will discuss versions of this theorem in the context of measurable graph combinatorics. I will mainly focus on the case when the graph in question is defined on a standard probability space \((X,\mu)\). In this situation, a combination of an augmenting chain technique developed earlier with Oleg Pikhurko (that was applied for graphings) together with a new result about quasi-invariant measures allows to deduce a full analogue of Vizing's theorem.
The Lovász Local Lemma is a classical tool in probabilistic combinatorics with numerous and diverse applications. In this talk, I will survey what is known about the behavior of the Local Lemma in the Borel and measurable context, including some very recent progress, and state several open problems. Part of this talk is based on joint work with Felix Weilacher.
This talk will survey the known structure of cardinalities below the power set of the first uncountable cardinal under various determinacy assumptions. Regularity and cofinality of cardinalities will be formulated. Combinatorial aspects of cardinalities such as primeness and Jónssonness may also be discussed. Portions of this talk includes joint work with Jackson and Trang.
In this talk I will explain how methods from logic allow one to construct refinements of classical algebraic invariants that are endowed with additional topological and descriptive set-theoretic information. This approach brings to fruition initial insights due to Eilenberg, Mac Lane, and Moore (among others) with the additional ingredient of recent advanced tools from logic. I will then present applications of this viewpoint to invariants from a number of areas in mathematics, including operator algebras, group theory, algebraic topology, and homological algebra.
Consider an action of a discrete group \(G\) on a compact, \(0\)-dimensional space \(X\). Its clopen type semigroup is an algebraic structure which encodes the equidecomposability relation between clopen subsets of \(X\) (two clopen subsets \(A,B\) of \(X\) are equidecomposable if there is a clopen partition \(A_1,\dots,A_n\) of \(A\) and elements \(g_1,\dots,g_n\) of \(G\) such that \(g_1 A_1,\dots, g_n A_n\) form a partition of \(B\)). I will discuss how some properties of the action can be studied via the clopen type semigroup; I will focus in particular on the dynamical comparison property (following Kerr and Ma), and the existence of a dense locally finite group in the topological full group associated to the action. I will also try to outline some consequences for generic properties of minimal actions of a given countable group on the Cantor space, and discuss some open problems.
The Solecki dichotomy in descriptive set theory, roughly stated, says that every Borel function on the real numbers is either a countable union of partial continuous functions or at least as complicated as the Turing jump. The Posner-Robinson theorem in computability theory, again roughly stated, says that every non-computable real looks like 0' relative to some oracle. Superficially, these theorems look similar: both roughly say that some object is either simple or as complicated as the jump. However, it is not immediately apparent whether this similarity is more than superficial. If nothing else, the Solecki dichotomy is about third order objects—functions on the real numbers—while the Posner-Robinson theorem is about second order objects—individual real numbers. We will show that there is a genuine mathematical connection between the two theorems by showing that the Posner-Robinson theorem plus determinacy can be used to give a short proof of a slightly weakened version of the Solecki dichotomy. We will explain the idea of this proof and then discuss its connections to some questions about well-foundedness of various reducibility notions on functions.
We say that a Polish group \(G\) has stronger classification strength than a Polish group \(H\) iff every orbit equivalence relation induced by a continuous action of \(H\) on a Polish space is Borel-reducible to an orbit equivalence relation induced by a continuous action of \(G\) on a Polish space (or in other words, "classified" by \(G\). The notion of classification strength gives a way to measure the inherent complexity of a Polish group, and gives rise to interesting hierarchies.
We say that \(G\) involves \(H\) iff there is a closed subgroup \(G'\) of \(G\) and a continuous surjective homomorphism from \(G'\) onto \(H\). If \(G\) involves \(H\) then it has greater classification strength, a result of Mackey and Hjorth. Also, a result of Hjorth implies that any Polish group which has greater classification strength than \(S_\infty\), the Polish group of permutations of a countably-infinite set, involves \(S_\infty\). In other words, the non-Archimedean Polish groups (i.e. the closed subgroups of \(S_\infty\)) with maximal classification strength are exactly those which involve \(S_\infty\).
We will describe several new necessary and sufficient conditions for a non-Archimedean Polish group to involve \(S_\infty\), some of which may have independent interest in model theory. One result of particular significance is that if \(G\) classifies \(=^+\), a natural equivalence relation very low in the Borel hierarchy, then \(G\) must involve \(S_\infty\). Moreover, a natural rank function of model-theoretic flavor arises, measuring how close a non-Archimedean Polish group is from involving \(S_\infty\), which yields an interesting hierarchy of classification strength. I will also mention previous and ongoing work with Aristotelis Panagiotopoulos relating to another hierarchy of classification strength among the cli (complete left-invariant) Polish groups.
The axiom of Dependent Choices (DC) and the axiom of Countable Choices (CC) play an important role in set theory. Both axioms admit a "local" version denoted by DC(X) and CC(X), meaning that the choices are made in a given set X. It is well known that DC implies CC, but does DC(X) imply CC(X) for any non-empty set X? (The question is obviously formulated in the choice-less context of ZF.) The answer is affirmative for many X, e.g. if X is in bijection with its square, but it is not true in general.
Theorem 1: Assume CC(R), where R is the set of real numbers. Then DC(X) implies CC(X) for all non-empty X.
Theorem 2: There is a model of ZF in which there is a subset X of R such that DC(X) holds and CC(X) fails.
The model of Theorem 2 is a symmetric extension using a forcing notion P that is hybrid between a product and an iteration.
This is joint work with Lorenzo Notaro.
A classical almost disjoint family is a family of subsets of the natural numbers such that any two non-identical elements of the family intersect finitely, that is, their intersection is in the ideal FIN. A "mad family" is, of course, a maximal almost disjoint family. Definability problems related to classical mad families have been studied intensively in the past few years. This talk is about extending and generalizing the classical notion of an almost disjoint family by replacing the ideal of finite sets \(\textrm{FIN}\) with other ideals, and in this talk, this specifically means replacing it with the iterated Frechet ideals \(\textrm{FIN}^2, \textrm{FIN}^3, \cdots\). We call mad families with respect to the iterated Frechet ideals "higher dimensional" mad families. In this talk, I will try to give a fairly detailed account of the argument in "dimension 2", i.e., when we consider \(\textrm{FIN}^2\). This is joint work with David Schrittesser.
One of the biggest open problems in mathematical physics has been the problem of formulating a complete and consistent theory of quantum gravity. Some of the core technical and epistemological difficulties come from the fact that General Relativity (GR) is fundamentally a geometric theory and, as such, it oughts to be "generally covariant", i.e., invariant under change of coordinates by any element of the diffeomorphism group \(\text{Diff}(M)\) of the ambient manifold \(M\). The Problem of Observables is a famous instance of the difficulties associated with general covariance, and one directly related to ineffectiveness of classical quantization recipes when it comes to GR. In a nutshell, the problem of observables asks whether GR admits a complete set of smooth observables. That is, whether the family of all diffeomorphism-invariant, real-valued, smooth maps on the space \(\text{Ein}(M)\) of all Einstein metrics on \(M\) is rich enough to separate all physical spacetimes. So far the only smooth observables known (when \(M={\mathbb R}^4)\) are the constant maps. In this talk, we will employ methods from descriptive set theory in order to answer the problem of observables in the negative. These results are inspired by old discussions with Marios Christodoulou and are based on recent work with George Sparling.
We use the projective Fraissé approach and Ramsey's theorem to show that the universal minimal flow of the homeomorphism group of the universal Knaster continuum is homeomorphic to the universal minimal flow of the free abelian group on countably many generators.
We will define a projective Fraissé class whose limit approximates the universal Knaster continuum in such a way that the group \(\textrm{Aut}(\mathbb{K})\) of automorphisms of the Fraissé limit is a dense subgroup of the group, \(\textrm{Homeo}(K)\), of homeomorphisms of the universal Knaster continuum. The computation of the universal minimal flow involves modifying the Fraissé class in a natural way so that it approximates an open, normal, extremely amenable subgroup of \(\textrm{Homeo}(K)\).
We give a method of producing a Polish module over an arbitrary subring of \(\mathbb Q\) from an ideal of subsets of \(\mathbb N\) and a sequence in \(\mathbb N\). The method allows us to construct two Polish \(\mathbb Q\)-vector spaces, \(U\) and \(V\), such that
– both \(U\) and \(V\) embed into \(\mathbb R\), but
– \(U\) does not embed into \(V\) and \(V\) does not embed into \(U\),
where by an embedding we understand a continuous \(\mathbb Q\)-linear injection. This construction answers a question of Frisch and Shinko. In fact, our method produces a large number of incomparable with respect to embeddings Polish \(\mathbb Q\)-vector spaces.
This is joint work with Slawomir Solecki.
Let \(G\) be a countably infinite group and let \(\text{Sub}_{G}\) be the compact space of subgroups \(H \leqslant G\). Then an invariant random subgroup (IRS) of \(G\) is a probability measure \(\nu\) on \(\text{Sub}_{G}\) which is invariant under the conjugation action of \(G\) on \(\text{Sub}_{G}\).
In this talk, after a brief introduction to the theory of invariant random subgroups, I will discuss some of the many basic questions in this relatively new area. For example, if \(\nu\) is an ergodic IRS of a countable group \(G\), then we obtain a corresponding zero-one law on \(\text{Sub}_{G}\) for the class of group-theoretic properties \(\Phi\) such that the set \(\{\, H \in \text{Sub}_{G} \mid H \text{ has property } \Phi \,\}\) is \(\nu\)-measurable; and thus \(\nu\) concentrates on a collection of subgroups which are quite difficult to distinguish between. Consequently, it is natural to ask whether there exists an ergodic IRS of a countable group \(G\) which does not concentrate on the subgroups \(H \leqslant G\) of a single isomorphism type.
In this talk, we will show that elementary bi-embeddability is an analytic complete equivalence relation under Borel reducibility by giving a reduction from the bi-embeddability relation on graphs. We will then discuss the degree spectra realized by these relations. The degree spectrum of a countable structure with respect to an equivalence relation \(E\), a central notion in computable structure theory, is the set of Turing degrees of structures \(E\)-equivalent to it. By analyzing the computability theoretic properties of our reduction from bi-embeddability to elementary bi-embeddability we show that the degree spectra of these two relations are related. Suppose a set of Turing degrees \(X\) is the bi-embeddability spectrum of a graph. Then the set of degrees whose Turing jump is in \(X\) is the elementary bi-embeddability spectrum of a graph. Combining results of Harrison-Trainor and the coauthor one sees that this is sharp: There is a bi-embedddability spectrum that is not an elementary bi-embeddability spectrum.
Given a finite relational language \(\mathcal L\) and a (possibly infinite) set \(\mathcal F\) of finite irreducible \(\mathcal L\)-structures, the class \(\operatorname{Forb}(\mathcal F)\) describes those finite \(\mathcal L\)-structures which do not embed any member of \(\mathcal F\). Classes of the form \(\operatorname{Forb}(\mathcal F)\) exactly describe those classes of finite \(\mathcal L\)-structures with free amalgamation. In recent joint work with Balko, Chodounsky, Dobrinen, Hubicka, Konecny, and Vena, we exactly characterize big Ramsey degrees for those classes \(\operatorname{Forb}(\mathcal F)\) where the forbidden set \(\mathcal F\) is finite. This characterization proceeds by defining tree-like objects called diagonal diaries, then showing that the big Ramsey degree of any \(A\) in \(\operatorname{Forb}(\mathcal F)\) is exactly the number of diagonal diaries which code the structure \(A\). After giving a brief description of these objects, the talk will then consider those infinite diagonal diaries which code the Fraisse limit of \(\operatorname{Forb}(\mathcal F)\). In upcoming joint work with Dobrinen, we prove a Galvin-Prikry theorem for any such infinite diagonal diary, giving new examples of objects satisfying the Galvin-Prikry theorem which dramatically fail to satisfy Todorcevic's Ramsey space axioms A1 through A4.
Kaleidoscopic groups are infinite permutation groups recently introduced by Duchesne, Monod, and Wesolek by analogy with a classical construction of Burger and Mozes of subgroups of automorphism groups of regular trees. In contrast with the Burger-Mozes groups, kaleidoscopic groups are never locally compact and they are realized as groups of homeomorphisms of Wazewski dendrites (tree-like, compact spaces whose branch points are dense). The input for the construction is a finite or infinite permutation group \(\Gamma\) and the output is the kaleidoscopic group \(K(\Gamma)\).
In this talk, I will discuss recent joint work with Gianluca Basso, in which we explain how these groups can be viewed as automorphism groups of homogeneous structures and characterize the universal minimal flow of \(K(\Gamma)\) in terms of the original group \(\Gamma\).
In the decade 1994 - 2004 I wrote five papers applying techniques from descriptive set theory to a question posed by the dynamics group of Barcelona concerning the possible lengths of iterations. In August 2021 I gave two talks in the CUNY set theory Zoominar of Vika Gitman which were largely devoted to expounding the last and hardest of my constructions in this area. The present talk will be devoted to my earlier and more basic results, some recent work, and various open problems which I hope might attract logicians working in areas such as the descriptive set theory of group actions.