We introduce a framework for studying "reasonable" classifying invariants, more permitting than "classification by countable structures". This framework respects the intuitions and results about classifications by countable structures, and allows for equivalence relations such as \(E_1\) and \(E_1^+\) to be "reasonably classifiable" as well. In this framework we show that \(E_1\) has classifying invariants which are \(\kappa\)-sequences of \(E_0\)-classes for \(\kappa = \mathfrak{b}\), and it does not have such classifying invariants if \(\kappa < \mathbf{add}(\mathcal{B})\).
The result relies on analysing the tail intersection model \(\bigcap_{n < \omega} V[c_n, c_{n+1}, \ldots]\), where \(\langle c_0, c_1, \ldots\rangle\) is a generic sequence of Cohen reals.
For every Polish permutation group \(P \le \operatorname{Sym}(\mathbb{N})\), let \(A \mapsto [A]_P\) be the assignment which maps every \(A \subseteq \mathbb{N}\) to the set of all \(k \in \mathbb{N}\) whose orbit under the action of the stabilizer \(P_F\) of some finite \(F \subseteq A\) is finite. Then \(A \mapsto [A]_P\) is a closure operator and hence it endows \(P\) with a natural notion of dimension \(\dim(P)\). This notion of dimension has been extensively studied in model theory when \(A \mapsto [A]_P\) satisfies additionally the exchange principle, that is, when \(A \mapsto [A]_P\) forms a pregeometry. However, under the exchange principle, every Polish permutation group \(P\) with \(\dim(P) < \infty\) is locally compact and therefore unable to generate any "wild" dynamics. In this talk, we will discuss the relationship between \(\dim(P)\) and certain strong ergodicity phenomena in the absence of the exchange principle. In particular, for every \(n \in \mathbb{N}\), we will provide a Polish permutation group \(P\) with \(\dim(P) = n\) whose Bernoulli shift \(P \curvearrowright \mathbb{R}^{\mathbb{N}}\) is generically ergodic relative to the injective part of the Bernoulli shift of any permutation group \(Q\) with \(\dim(Q) < n\). We will use this to exhibit an equivalence relation of pinned cardinal \(\aleph_1\) which strongly resembles Zapletal's counterexample to a question of Kechris, but which does not Borel reduce to the latter. Our proofs rely on the theory of symmetric models of choiceless set theory and in the process we establish that a vast collection of symmetric models admit a theory of supports similar to the basic Cohen model. This is joint work with Assaf Shani.
Given an \(L_{\omega_1\omega}\)-sentence \(\varphi\) in a countable language, we call an ergodic \(S_\infty\)-invariant probability measure on the Borel space of countable models of \(\varphi\) (having fixed underlying set) an ergodic model of \(\varphi\). I will discuss the number of ergodic models of such a sentence \(\varphi\), including the case when \(\varphi\) is a Scott sentence. This is joint work with N. Ackerman, C. Freer, A. Kruckman and A. Kwiatkowska.
A directed hypergraph \(G\) consists of a vertex set \(V\) along with a collection of directed hyperedges \((A, B)\), where \(A\) and \(B\) are finite subsets of \(V\). Given a set of vertices \(X\), we think of the edge \((A, B)\) as being on the boundary of \(X\) if \(X\) intersects \(A\) and does not completely contain \(B\).
We can generalize the notion of directed hypergraph as follows. A filter graph \(G\) consists of an infinite vertex set \(V\) along with a collection of edges \((F, G)\), where \(F\) and \(G\) are filters on \(V\). Given a set of vertices \(X\), we think of the edge \((F, G)\) as being on the boundary of \(X\) if \(X\) is \(F\)-positive and the complement of \(X\) is \(G\)-positive.
Filter graphs seem to be surprisingly graph-like. We'll show that filter graphs satisfy the natural generalization of the max-flow/min-cut theorem, where point masses flowing along directed edges in the usual hypergraph setting are replaced by ultrafilters flowing along filter-edges.
One of the numerous strengthenings of Ramsey's theorem is due to Erdős and Rado, who analyzed what partition properties can be obtained on \(m\)-subsets of the naturals when colorings are not necessarily finite. Large monochromatic sets may not appear in that case, but there is a finite list of behaviors, called "canonical", to which every coloring reduces. The purpose of this talk will be to remind certain not so well-known analogous theorems of the same flavor that were obtained by Prömel in the eighties for various classes of structures (like graphs or hypergraphs), and to show how such theorems can in fact be deduced in the more general setting of Fraïssé classes.
The talk will be devoted to the isomorphism relations on Borel classes of locally compact Polish metric structures. Using continuous logic, one can prove that they are always Borel reducible to graph isomorphism, which implies, in particular, that isometry of locally compact Polish metric spaces is reducible to graph isomorphism. This answers a question of Gao and Kechris. As a matter of fact, locally compact Polish metric structures behave very much like countable ones. For example, Hjorth, Kechris and Louveau proved that isomorphism of countable structures that is potentially of rank \(\alpha + 1\) multiplicative Borel class is reducible to equality on hereditarily countable sets of rank \(\alpha\), and the same turns out to be true about locally compact Polish metric structures. Time permitting, I will also discuss certain variants of the Hjorth-isomorphism game, recently introduced by Lupini and Panagiotopoulos.
The point-to-set principle has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces \(\mathbb{R}^n\). These are classical questions, meaning that their statements do not involve computation or related aspects of logic.
In this talk I will describe the extension of two algorithmic fractal dimensions --- computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions \(\dim(x)\) and \(\operatorname{Dim}(x)\) to individual points \(x\in X\) --- to arbitrary separable metric spaces and to arbitrary gauge families. I will then discuss the extension of the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. Finally, I will indicate how the extended point-to-set principle can be used to prove new theorems about classical fractal dimensions in hyperspaces.
This is joint work with Neil Lutz and Elvira Mayordomo.
Let \(X\) and \(Y\) be two topological spaces. Given a subset \(A\) of \(X\) and a subset \(B\) of \(Y\) we say that \(A\) is Wadge-reducible (or sometimes continuously reducible) to \(B\) if there is a continuous function \(f\) from \(X\) to \(Y\) that satisfies \(f^{-1}(B)=A\). Wadge reducibility is a particularly nice quasi-order on subsets of Polish zero-dimensional spaces: Wadge's Lemma guarantees indeed that its antichains are of size at most two, while Martin and Monk have proven that it is well-founded. This gives an ordinal ranking to every equivalence class for Wadge reducibility, thus generating various questions. I will talk about two of these questions.
First, given a Wadge equivalence class, can we build it using classes of lower ordinal rank, and how?
Second, given any Polish zero-dimensional space \(X\), can we decide if there is an antichain of two classes or just one class of some specific ordinal rank of the Wadge quasi-order of \(X\)? For which ranks?
I will talk about an ongoing work in which new reasons of non-hypersmoothness are investigated. I will present an \(F_\sigma\) equivalence relation, which is not hypersmooth because of a Ramsey-theoretic argument.
The talk is a meld of two papers, both joint with Douglas Ulrich.
We characterize which \(\Phi \in \mathcal{L}_{\omega_1, \omega}\) have Borel complete expansions and give several sufficient conditions for a theory to have a Borel complete reduct, e.g., having uncountably many complete \(1\)-types.
We illustrate these general behaviors by considering a family \(T_h\) of first-order theories, indexed by functions \(h \colon \omega \rightarrow \omega \setminus \{0, 1\}\) in a language \(L = \{E_n : n \in \omega\}\) asserting that each \(E_n\) is an equivalence relation with \(h(n)\) classes, and that the classes cross-cut. The key to showing that many theories have Borel complete reducts follows from the fact that \(T_h\) is Borel complete whenever \(h\) is unbounded. We deduce our equivalents of having a Borel complete expansion in order to show the converse: if \(h\) is bounded, then \(T_h\) is not Borel complete.
An orbit equivalence between Borel actions of Polish groups is a Borel bijection between phase spaces that preserves orbit partitions. We are interested in free \(\mathbb{R}^m\)-actions which are known as multidimensional flows. In this case, orbit equivalence is a coarse invariant collapsing all non-trivial flows into one class. Since any translation-invariant structure can be transferred from the acting group onto individual orbits, it is natural to consider strengthenings of orbit equivalence that respect these structures. Notable examples of such structures include measure, topology, and metric.
We will concentrate on two instances of this paradigm and discuss Borel versions of two ergodic-theoretical results: Katok's representation theorem and Rudolph's result on smooth orbit equivalence. The latter shows that any non-trivial free \(\mathbb{R}^m\)-flow can be transformed into any other \(\mathbb{R}^m\)-flow via an orbit equivalence that is a smooth orientation-preserving diffeomorphism on each orbit. Katok's theorem provides a multidimensional generalization of the suspension flow construction and shows that all free \(\mathbb{R}^m\)-flows emerge as special flows over \(\mathbb{Z}^m\)-actions.
We discuss a few new results concerning the descriptive combinatorics of bounded degree hyperfinite Borel graphs. In particular, we show that the Baire measurable edge chromatic number of \(G\) is at most \(\left\lceil\frac{3}{2}\Delta(G)\right\rceil+6\) when \(G\) is a multigraph, and for bipartite graphs we improve this bound to \(\Delta(G)+1\) and show that degree regular one-ended bipartite graphs have Borel perfect matchings generically. Similar results hold in the measure setting assuming some hyperfiniteness conditions. This talk is based on joint work with Kun and Sabok, Weilacher, and upcoming work with Poulin and Zomback.
According to the Connes-Feldman-Weiss theorem, measurable amenability is equivalent to measurable hyperfiniteness for countable group actions It is easy to see that Borel hyperfiniteness implies Borel amenability, but the opposite direction is a very hard open problem (Jackson-Kechris-Louveau).
The graph-theoretical analogue of amenability is clearly Property A. One can view the so-called uniform local amenability (ULA) property (or local Følner-property) as the graph-theoretical analogue of hyperfiniteness. Brodzky et al. proved that Property A implies ULA. Two years ago I was able to prove that, in fact, ULA is equivalent to Property A. This result has an interesting application in distributed computing.
We say that an action is Uniformly (measurably) Hyperfinite, if all the positive measure subgraphings of the graphing of the action is hyperfinite with the same structure constants. I recently proved that Uniform Hyperfiniteness is equivalent to Uniform Amenability (the measurable version of Property A). Note that UA \(\implies\) UH is very similar to the Connes-Feldman-Weiss proof, UH \(\implies\) UA requires some new ideas.
A family of infinite subsets of natural numbers is
In joint work with Asger Törnquist, we managed to simplify the derivative process so that it can be carried out (and it terminates) in \(L_{\omega_1^{CK}}\), thus proving that for any infinite \(\Sigma^1_1\) almost disjoint family, there is a \(\Delta^1_1\) witness to non-maximality (where both classes are lightface). The ongoing work in progress attempts to generalise the result to the ideals \(\mathrm{Fin}^\alpha\) for \(\alpha < \omega_1^{CK}\).
This is joint work with Asger Törnquist.
Jens Mammen (Professor Emeritus of psychology at Aarhus and Aalborg University) has developed a theory in psychology, which aims to provide a model for the interface between a human being (and mind), and the real world.
This theory is formalized in a very mathematical way: Indeed, it is described through a mathematical axiom system. Realizations ("models") of this axiom system consist of a non-empty set \(U\) (the universe of objects), as well as a perfect Hausdorff topology \(S\) on \(U\), and a family \(C\) of subsets of \(U\) which must satisfy certain axioms in relation to \(S\). The topology \(S\) is used to model broad categories that we sense in the world (e.g., all the stones on a beach) and the \(C\) is used to model the process of selecting an object in a category that we sense (e.g., a specific stone on the beach that we pick up). The most desirable kind of model of Mammen's theory is one in which every subset of \(U\) is the union of an open set in \(S\) and a set in \(C\). Such a model is called "complete".
The harder mathematical aspects of Mammen's theory were first studied in detail by J. Hoffmann-Joergensen in the 1990s. Hoffmann-Joergensen used the Axiom of Choice (AC) to show that a complete model of Mammen's axiom system, in which the universe \(U\) is infinite, does exist. Hoffmann-Joergensen conjectured at the time that the existence of a complete model of Mammen's axioms would imply the Axiom of Choice.
I will discuss the set-theoretic aspects of complete Mammen models. First of all, the question of "how much" AC is needed to obtain a complete Mammen model; secondly, I will introduce some cardinal invariants related to complete Mammen models and establish elementary \(\mathsf{ZFC}\) bounds for them, as well as some consistency results.
This is joint work with Jens Mammen.
In the 1920s, Lusin asked whether every Borel function on a Polish space is a union of countably many partial continuous functions (i.e. whether every Borel function is \(\sigma\)-continuous). This question has a negative answer; an example of a non-piecewise continuous Borel function is the Turing jump. A dichotomy of Solecki and Zapletal is that the Turing jump is the basis for every counterexample: every Borel function \(f\) is either \(\sigma\)-continuous, or the Turing jump continuously reduces to \(f\).
We generalize the Solecki-Zapletal dichotomy throughout the Borel hierarchy. Recall that a Borel function is Baire class \(\alpha\) if and only if it is \(\mathbf\Sigma^0_{\alpha+1}\)-measurable. We show that every Borel function \(f\) is either \(\sigma\)-Baire class \(\alpha\), or a complete Baire class \(\alpha+1\) function (an appropriate iterate of the Turing jump) continuously reduces to \(f\). Our proof uses an adaptation of Montalbán's game metatheorem for priority arguments to boldface descriptive set theory.
This is joint work with Antonio Montalbán.
The correspondence between Ramsey theory, Fraïssé theory, and dynamics established in 2003 by Kechris, Pestov, and Todorčević has had far-reaching consequences in the study of automorphism groups of discrete first-order structures. The dual notion, projective Fraïssé theory (developed by Irwin and Solecki in 2006), considers classes of topological structures and in 2017, Panagiotopoulos proved that every compact, metrizable space can be obtained as a quotient of a projective Fraïssé limit. Therefore, projective Fraïssé theory provides an ideal framework to consider the homeomorphism groups of compact spaces. In this talk, for each Knaster continuum \(K\), we will give a projective Fraïssé class of finite objects that approximates \(K\) (up to homeomorphism) and use the dual of the KPT correspondence (proved by Bartošová and Kwiatkowska, 2018) to determine if the homeomorphism group of \(K\) is extremely amenable.
The talk will consist of two parts. In the first one, we introduce a certain natural Polish space of all separable Banach spaces. We compare it with the recent different approach to topologizing the space of separable Banach spaces, by Godefroy and Saint-Raymond.
Our main interest will be in the descriptive complexity of classical Banach spaces with respect to this Polish topology. We show that the separable infinite-dimensional Hilbert space is characterized as the unique Banach space whose isometry class is closed, and also as the unique Banach space whose isomorphism class is \(F_\sigma\), where the former employs the Dvoretzky theorem and the latter the solution to the homogeneous subspace problem. For \(p\) in \([1,\infty)-\{2\}\), we mention that the isometry class of \(L^p[0,1]\) is \(G_\delta\)-complete and the class of \(\ell^p\) is \(F_{\sigma, \delta}\)-complete.
In the second part, we connect it with the recent study of Fraïssé Banach spaces, initiated by Ferenczi, López-Abad, Mbombo, and Todorčević. We show that a Banach space has a comeager isometry class in its closure if and only if it is the unique limit of a 'weak Fraïssé class' of finite-dimensional spaces. While it is open whether there are other Fraïssé Banach spaces besides the Gurariĭ space and the \(L^p\)'s, we show there are more examples of generic Banach spaces in the weaker sense above.
The first part will be based on joint work with M. Doležal, M. Cúth, and O. Kurka; the second is a work in progress jointly with M. Cúth and N. de Rancourt.
I will talk about my recent result joint with S. Shelah establishing that the Borel space of torsion-free abelian groups with domain \(\omega\) is Borel complete, i.e., that the isomorphism relation on this Borel space is as complicated as possible, as an isomorphism relation. This solves a long-standing open problem in descriptive set theory, which dates back to the seminal paper on Borel reducibility of Friedman and Stanley from 1989. Time permitting, I will also talk about some recent results (also joint with S. Shelah) on the existence of uncountable Hopfian and co-Hopfian abelian groups and on anti-classification results for the countable co-Hopfian abelian and \(2\)-nilpotent groups. In particular, we will see that the countable co-Hopfian groups are complete co-analytic in the Borel space of \(2\)-nilpotent groups with domain \(\omega\). This solves an open question of Thomas, who had posed the question for the space of all groups with domain \(\omega\).
Which Borel quasi-orders are Borel reducible to Turing reducibility? In any such quasi-order, every element must have at most countably many predecessors (in which case we say the quasi-order is locally countable), but are there any other restrictions? It turns out that there are. It follows from recent work by Siskind and me that not every locally countable Borel quasi-order is Borel reducible to Turing reducibility. A more careful analysis shows that even fairly simple quasi-orders are not always reducible to Turing reducibility. I will discuss a few such examples as well as the broader context for this question. This talk contains joint work with Benjamin Siskind and Kojiro Higuchi.
Of the principles just slightly weaker than \(\mathsf{ATR}\), the most well-known are the theories of hyperarithmetic analysis (THA). By definition, such principles hold in \(HYP\). Motivated by the question of whether the Borel dual Ramsey theorem is a THA, we consider several theorems involving Borel sets and ask whether they hold in \(HYP\). To make sense of Borel sets without \(\mathsf{ATR}\), we formalize the theorems using completely determined Borel sets. We characterize the completely determined Borel subsets of \(HYP\) as precisely the sets of reals which are \(\Delta^1_1\) in \(L_{\omega_1^{ck}}\). Using this, we show that in \(HYP\), Borel sets behave quite differently than in reality. For example, in \(HYP\), the Borel dual Ramsey theorem fails, every \(n\)-regular Borel acyclic graph has a Borel \(2\)-coloring, and the prisoners have a Borel winning strategy in the infinite prisoner hat game. Thus the negations of these statements are not THA. Joint work with Henry Towsner and Rose Weisshaar.
The axiom of real determinacy (\(\mathsf{AD}_\mathbb{R}\)) asserts the determinacy of every infinite two-player, perfect-information game with moves in the set of real numbers. By a theorem of Woodin, \(\mathsf{ZF} + \mathsf{AD}_\mathbb{R}\) is consistent if and only if \(\mathsf{ZFC}\) is consistent together with the existence of a cardinal \(\lambda\) which is a limit of Woodin cardinals and \({<}\lambda\)-strong cardinals.
In this talk, we explore the strength of \(\mathsf{AD}_\mathbb{R}\) over the theory \(\mathsf{KP} + \unicode{x201C}\textrm{\(\mathbb{R}\) exists}\unicode{x201D}\) and observe that it is much weaker. Indeed, the theory \(\mathsf{KP} + \mathsf{AD}_\mathbb{R} + \unicode{x201C}\textrm{\(\mathbb{R}\) exists}\unicode{x201D}\) is weaker than \(\mathsf{ZFC} + \unicode{x201C}\textrm{there are \(\omega^2\) Woodin cardinals}\unicode{x201D}\). This is a consequence of the following theorem: over \(\mathsf{ZFC}\), the existence of a transitive model of \(\mathsf{KP} + \mathsf{AD}_\mathbb{R}\) containing the set of all real numbers is equivalent to the determinacy of all open games of length \(\omega^3\).
We will describe how the perspectives of Recursion Theory and Set Theory suggest lines of investigation into Geometric Measure Theory. We will discuss the extent of capacitability for Hausdorff dimension and the question of existence of sets of strong gauge dimension, which is a property generalizing that of strong measure zero.
Every continuous action of a countable group on a Polish space induces a Borel equivalence relation. We are interested in the problem of realizing (i.e. finding a Borel isomorphic copy of) these equivalence relations as continuous actions on compact spaces. We provide a number of positive results on this problem, and we investigate the connection to subshifts. Joint with Joshua Frisch, Alexander Kechris and Zoltán Vidnyánszky.
There are several well-studied "jumps" on the class of Borel equivalence relations under Borel reducibility, namely, the Friedman-Stanley jump and the family of Louveau jumps. In joint work with John Clemens, we defined a new(ish) family of jumps called Bernoulli jumps. In this talk I will introduce and describe Bernoulli jumps, and present an application to the classification of countable scattered orders. I will conclude by summarizing some recent developments (due to Shani and Allison) on Bernoulli jumps.
For a given finite relational structure \(\mathcal R\), the associated constraint satisfaction problem (or CSP) is the problem of testing when a structure admits a homomorphism into \(\mathcal R\). The algebraic approach studies a CSP by considering its algebra of so-called polymorphisms, operations (of all arities) which preserve the relations in \(\mathcal R\). This approach has led to many classification results. For instance, CSPs solvable by polynomial time algorithms, linear relaxation, and constraint propagation have all been classified. In this talk I will present partial results towards similar classifications of Borel CSPs with various descriptive set theoretic properties: those problems which are \(\mathbf \Pi^1_1\) in the codes, effectivizable, or equivalent to their classical version.
Marks proved the existence of \(d\)-regular acyclic Borel graphs with Borel chromatic number \(d+1\). It can be shown that such statements cannot be proved using measures or Baire category, and, indeed, the Borel determinacy theorem had to be invoked.
We discuss a generalization of Marks' method, which leads to an interesting new class of examples of \(3\)-regular acyclic Borel graphs, which we call homomorphism graphs.
This yields new proofs of a number of known results. As a new application, we show that it is hard to decide whether the Borel chromatic number of a Borel graph is \(\le 3\), even for acyclic \(3\)-regular graphs (that is, such graphs form a \(\mathbf\Sigma^1_2\)-complete set).
Joint work with Jan Grebík.
We go through the history of measurable perfect matchings from the Banach-Tarski paradox via circle squaring and report on recent progress. We construct a \(d\)-regular treeing (for every \(d > 2\)) without a measurable perfect matching. We show that the Hall condition is essentially sufficient in the hyperfinite, one-ended, bipartite case. This allows us to characterize bipartite Cayley graphs with factor of i.i.d. perfect matchings extending the Lyons-Nazarov theorem. We apply these to Gardner's conjecture for uniformly distributed sets, to balanced orientations, and to get new, simple proofs of the measurable circle squaring. We prove the analogous theorems in the context of rounding flows, too. Partially joint work with Matt Bowen and Marcin Sabok.
Blanchard introduced the concepts of Uniform Positive Entropy (UPE) and Complete Positive Entropy (CPE) as topological analogues of K-automorphism. He showed that UPE implies CPE, and that the converse is false. A flurry of recent activity studies the relationship between these two notions. For example, one can assign a countable ordinal which measures how complicated a CPE system is. Recently, Barbieri and García-Ramos constructed Cantor CPE systems at every level of CPE. Westrick showed that natural rank associated to CPE systems is actually a \(\Pi^1_1\)-rank. More importantly, she showed that the collection of CPE \(\mathbb Z^2\)-SFT's is a \(\Pi^1_1\)-complete set. In this talk, we discuss some results, where UPE and CPE coincide and others where we show that the complexity of certain classes of CPE systems is \(\Pi^1_1\)-complete. This is joint work with García-Ramos.
It is a nice exercise in combinatorics to show that every \(2d\)-regular finite graph arises as a Schreier graph of the free group \(F_d\). I will present generalizations of this fact to a measurable setting, as well as some examples showing the limitations. I will formulate these results using both the language of unimodular random networks and that of (p.m.p.) graphings, which are two sides of the same coin. Partially joint work with Ferenc Bencs and Aranka Hrušková.
A well-known result of Giordano-Putnam-Skau asserts that two minimal homeomorphisms of the Cantor space which have the same invariant Borel probability measures are orbit equivalent. I will present a new, rather elementary, proof of that fact, based on a strengthening of a 1979 theorem of Krieger concerning minimal actions of certain locally finite groups on the Cantor space. No familarity with topological dynamics will be assumed.
This is joint work with Simon Robert (Lyon).
We are interested in generalizations of some theorems of ergodic theory to the Borel context, particularly for natural spaces of tilings, colorings and Hamilton paths. The work combines dynamical properties of actions of \(\mathbb Z^d\) with the finite combinatorics of the \(\mathbb Z^d\) lattice. This is joint work with Nishant Chandgotia.
Let \(F\) be a nonabelian free group. We show that, for any two nontrivial finite groups, the natural actions of the wreath product groups \(A\wr F\) and \(B\wr F\), on \(A^F\) and \(B^F\) respectively, are orbit equivalent. On the other hand, we show that these actions are not even stably orbit equivalent if \(F\) is replaced with any ICC sofic group with property (T), and \(A\) and \(B\) have different cardinalities. This is joint work with Konrad Wrobel.
Working in the framework of Borel reducibility, we analyze the complexity of the natural counterparts in terms of quasi-orders of the well-known relations of equivalence for arcs and knots. It turns out that this problem is related to the study of convex embeddability between countable linear orders (and of its analogue for circular orders), which is a topic of independent interest. This is work in progress, joint with Iannella, Kulikov and Marcone.
I will present a dichotomy for equivalence relations on Polish spaces that can be expressed as countable unions of smooth Borel subequivalence relations. It can be seen as an extension of Kechris-Louveau's dichotomy for hypersmooth Borel equivalence relations. A generalization of our dichotomy, for equivalence relations that can be expressed as countable unions of Borel equivalence relations belonging to certain fixed classes, will also be presented. This is a joint work with Benjamin Miller.
A countable group is highly transitive if it admits an embedding in the permutation group of the integers with dense image. I will present a joint work with Pierre Fima, Soyoung Moon and Yves Stalder where we show that a large class of groups acting on trees are highly transitive, which yields a characterization of high transitivity for groups admitting a minimal faithful action of general type on a tree thanks to the work of Le Boudec and Matte Bon. Our proof is new even for the free group on two generators and I will give a detailed overview in this very particular case, showing that the generic transitive action of the free group on two generators is highly transitive.
In this talk I will discuss the structure of the relation of continuous reducibility on affine varieties. If time permits, I will also present some results on polynomial reducibility. The results are joint work with C. Massaza.
The group \(\operatorname{PL}_o I\) of piecewise linear orientation preserving homeomorphisms of the unit interval, equipped with composition, has a rich array of finitely generated subgroups. A basic question one can ask is when one of these groups embeds into another. One group which seems to play a particularly important role in this quasi-order is Richard Thompson's group \(F\). For instance it is conjectured that every finitely generated subgroup of \(\operatorname{PL}_o I\) either contains a copy of \(F\) or else embeds into \(F\). I will describe a general dynamical criterion for when a subgroup of \(\operatorname{PL}_o I\) does not embed into \(F\) which covers all known examples. This is joint work with James Hyde.
Analogues of the infinite Ramsey Theorem to infinite structures have been studied since the 1930s, when Sierpiński gave a coloring of pairs of rationals into two colors such that, in any subset of the rationals forming a dense linear order, both colors persist. In the 1970s Galvin showed that two is the optimum number for pairs of rationals, while Erdős, Hajnal and Pósa extended Sierpiński's result to colorings of edges in the Rado graph. The next several decades saw a steady advance of results for other structures, a pinnacle of which was the 2006 work of Laflamme, Sauer, and Vuksanović, characterizing the exact number of colors for unavoidable colorings of finite graphs inside the Rado graph, and for similar Fraïssé structures with finitely many binary relations, including the generic tournament. This exact number is called the "big Ramsey degree", a term coined by Kechris, Pestov, and Todorčević.
In this talk, we will provide a brief overview of the area of big Ramsey degrees infinite structures. Then we will present recent joint work with Coulson and Patel, showing that free amalgamation classes, in which any forbidden substructures are \(3\)-irreducible, have big Ramsey degrees which are simply characterized. These results extend to certain strong amalgamation classes as well, extending the results of Laflamme, Sauer, and Vuksanović. This is in contrast to the more complex characterization of big Ramsey degrees for binary relational free amalgamation classes with forbidden \(2\)-irreducible substructures, obtained in joint work of the speaker with Balko, Chodounský, Hubička, Konečný, Vena, and Zucker. The work with Coulson and Patel develops coding trees of quantifier-free \(1\)-types and uses forcing to do an unbounded search for monochromatic finite objects. Furthermore, we work with skew subtrees with branching degree two which still code the Fraïssé limit. This allows for more ease when working with relations of arity greater than two, and also allows us to give the first proof of exact big Ramsey degrees bypassing the standard method of "envelopes". It also sets the stage for current work of the speaker on infinite-dimensional Ramsey theory, in the vein of Galvin-Příkrý, for Fraïssé limits of free amalgamation classes in which any forbidden substructures are \(3\)-irreducible.
A definable pair of disjoint non-\(\mathrm{OD}\) sets of reals (hence, indiscernible sets) exists in the Sacks and \(E_0\)-large generic extensions of the constructible universe \(L\). More specifically, if \(a\) is a real either Sacks generic or \(E_0\) generic over \(L\), then it is true in \(L[a]\) that: there is a \(\Pi^1_2\) equivalence relation \(Q\) on the set \(U\), of all nonconstructible reals, with exactly two equivalence classes, and both those classes are non-\(\mathrm{OD}\) sets. This is joint work with Ali Enayat.
There are deep connections between model theory of the infinitary logic \(\mathcal{L}_{\omega_1 \omega}\) and descriptive set theory: Scott analysis, the López-Escobar theorem or the Suzuki theorem are well known examples of this phenomenon. In this talk, I would like to present results of an ongoing research devoted to generalizing these connections to the setting of continuous infinitary logic and Polish metric structures. In particular, I will discuss a continuous counterpart of a theorem of Hjorth and Kechris characterizing essential countability of the isomorphism relation on a given Borel class of countable structures. As an application, I will give a short model-theoretic proof of a result of Kechris saying that orbit equivalence relations induced by continuous actions of locally compact Polish groups are essentially countable. This is joint work with Andreas Hallbäck and Todor Tsankov.
In this talk we shall discuss some anticlassification results for orderable groups. First, we introduce the space of Archimedean orderings \(\operatorname{Ar}(G)\) for a given countable orderable group \(G\). We prove that the equivalence relation induced by the natural action of \(\operatorname{GL}_2(\mathbb{Q})\) on \(\operatorname{Ar}(\mathbb{Q}^2)\) is not concretely classifiable. Then we shall discuss the complexity of the isomorphism relation for countable ordered Archimedean groups. In particular, we show that its potential class is not \(\mathbf{\Pi}^0_3\). This topological constraint prevents classifying ordered Archimedean groups using countable subsets of reals. Our proofs combine classical results on Archimedean groups, the theory of Borel equivalence relations, and analyzing definable sets in the basic Cohen model and other models of Zermelo-Fraenkel set theory without choice. This is joint work with Dave Marker, Luca Motto Ros, and Assaf Shani.
We discuss our result with András Máthé and Jonathan Noel that a disk in the plane can be partitioned into finitely many Jordan measurable pieces that can be moved by translations to form a partition of a square.
We discuss two equivalence relations for diffeomorphisms of finite dimensional smooth manifolds. The first is measure isomorphism between ergodic Lebesgue measure preserving diffeomorphisms of the \(2\)-torus. The second is topological conjugacy for diffeomorphisms of smooth manifolds. In both cases we show that the equivalence relation is unclassifiable. For topological conjugacy, for dimension \(\ge 2\) we can embed \(E_0\), while for dimension \(\ge 5\) we can embed graph isomorphism.
We finish by showing that the equivalence relations are \(\Pi^0_1\)-hard: for measure preserving diffeomorphisms of the torus we exhibit a primitive recursive association of \(\Pi^0_1\)-statements with diffeomorphisms of the torus so that for each \(\phi\),
We consider interesting descriptive set-theoretic problems emerging from theoretical economics. First, we investigate a certain two-player game coming from gambling theory. Then, as a by-product, we obtain a novel game that characterises the Baire class 1 functions. We mention how games can be used to define new natural ranks on the Baire class 1 functions. Finally, we determine the exact complexity of the so-called value of the above game, which turns out to be a less well-known class, namely analytic-inductive.
The three problems referred to in the title originate in operator algebras, quantum information theory, and complexity theory respectively. Recently we established the complexity-theoretic equality \(\mathsf{MIP}^* = \mathsf{RE}\). This equality implies that the membership problem for certain quantum correlation sets is undecidable. Due to prior work by many others, the result implies a negative answer to Tsirelson's problem (quantum information) as well as Connes' embedding problem (von Neumann algebras) and equivalent problems in operator algebras such as Kirchberg's QWEP (C*-algebras). It leaves open the famous question about the existence of a non-hyperlinear group.
In the talk, I will explain the characterization \(\mathsf{MIP}^* = \mathsf{RE}\) and motivate it by describing its connection to the study of nonlocality in quantum information, Tsirelson's problem, and operator algebras. I will mention some proof ideas, which draw from the theory of probabilistic checking in complexity theory and approximate stability in group theory.
The main result is joint work with Ji, Natarajan, Wright and Yuen available as arXiv:2001.04383.
Generalizing a Urysohn-like extension property for Hall's countable universal locally finite group, we define a concept of omnigenous groups and prove some results about such groups. One of the main results is that any countable omnigenous locally finite group can be embedded as a dense subgroup of the isometry group of the Urysohn space for all \(\Delta\)-metric spaces, for any countable distance value set \(\Delta\). This implies a conjecture of Vershik from 2008. I will also talk about the current progress on the converse problem, namely to characterize all countable (locally finite) dense subgroups of the isometry groups of Urysohn spaces. This is joint work with Mahmood Etedadialiabadi, Francois Le Maître, and Julien Melleray.
We present a method for showing that a given \(\mathbf\Pi^0_3\) subset of a Polish space is in fact \(\mathbf\Pi^0_3\)-complete. This is motivated by some questions from V. Nestoridis about the sequential spaces \(\ell^p\) and more generally about families of \(F\)-spaces \((X_i)_{i \in (I, \preceq)}\) that form \(\subseteq\)-chains, where \(\preceq\) is a linear ordering.
The intersection \(\cap_{p > a} \ell^p\) is known to be a \(\mathbf\Pi^0_3\) subset of \(\ell^q\) for all \(a, q\) with \(0 \le a < q < \infty\) (Nestoridis). We show that it is in fact a \(\mathbf\Pi^0_3\)-complete set. It turns out the proof can be generalized to the context of Polish spaces with no additional structure like linearity. This gives a method for showing \(\mathbf\Pi^0_3\)-completeness and in fact there are strong indications that it also gives a characterization of the latter property.
The first interesting case of a non-trivial, metrizable universal minimal flow (UMF) of a Polish group was computed by Pestov who proved that the UMF of the homeomorphism group of the circle is the circle itself. This naturally led to the question whether a similar result is true for homeomorphism groups of other manifolds (or more general topological spaces). A few years later, Uspenskij proved that the action of a group on its UMF is never 3-transitive, thus giving a negative answer to the question for a vast collection of topological spaces. Still, the question of metrizability of their UMFs remained open and he asked specifically whether the UMF of the homeomorphism group of the Hilbert cube is metrizable. We give a negative answer to this question for the Hilbert cube and all closed manifolds of dimension at least 2, thus showing that metrizability of the UMF of a homeomorphism group is essentially a one-dimensional phenomenon. This is joint work with Yonatan Gutman and Andy Zucker.
Christensen's Haar null ideal is a well-behaved generalization of Haar null sets to groups, which admit no Haar measure. We show that in the group \(\mathbb Z^\omega\), every Haar positive (that is, non-Haar null) analytic set contains a Haar positive closed set. Using this result, we determine the exact Wadge class of the family of Haar null closed subsets of \(\mathbb Z^\omega\).
I will present an introduction from the perspective of Borel complexity theory to the classification problem for extension of C*-algebras, its motivations from operator theory, and its connections with homological algebra.
In this, the second of a three-part series of talks, we describe a "definable Čech cohomology theory" strictly refining its classical counterpart. As applications, we show that, in strong contrast to its classical counterpart, this definable cohomology theory provides complete homotopy invariants for mapping telescopes of \(d\)-tori and of \(d\)-spheres; we also show that it provides an equivariant homotopy classification of maps from mapping telescopes of \(d\)-tori to spheres, a problem raised in the \(d = 1\) case by Borsuk and Eilenberg in 1936. These results build on those of the first talk. They entail, for example, an analysis of the phantom maps from a locally compact Polish space \(X\) to a polyhedron \(P\); instrumental in that analysis is the definable \(\operatorname{lim}^1\) functor. They entail more generally an analysis of the homotopy relation on the space of maps from \(X\) to \(P\), and we will begin by describing a category particularly germane for this analysis. Time permitting, we will conclude with some discussion and application of a related construction, namely that of the definable homotopy groups of a locally compact Polish space \(X\).
This is joint work with Martino Lupini and Aristotelis Panagiotopoulos.
This is the first talk in a three-part series in which we illustrate how classical invariants of homological algebra and algebraic topology can be enriched with additional descriptive set-theoretic information.
In the first talk we will focus on the "definable enrichment" of the first derived functors of \(\operatorname{Hom}(-,-)\) and \(\operatorname{lim}(-)\). We will show that the resulting "definable \(\operatorname{Ext}(B,F)\)" for pairs of countable abelian groups \(B, F\); and the "definable \(\operatorname{lim}^1(A)\)" for towers \(A\) of Polish abelian groups substantially refine their purely algebraic counterparts. In the process, we will develop an Ulam stability framework for quotients of Polish groups \(G\) by Polishable subgroups \(H\) and we will provide several rigidity results in the case where the ambient Polish group \(G\) is abelian and non-archimedean. A special case of our rigidity results answers a question of Kanovei and Reeken regarding quotients of the \(p\)-adic groups.
This is joint work with Jeffrey Bergfalk and Martino Lupini.
In the theory of unitary group representations, the following theorem of Elmar Thoma from the early 1960s is fundamental: A countable discrete group is "type I" if and only if it has an abelian finite index subgroup. By way of a celebrated theorem of Glimm from the same period, a group being "type I" is equivalent to saying that the irreducible unitary representations of the group admits a smooth classification in the familiar sense of Borel reducibility, and in fact they are all finite-dimensional in this case. Glimm's theorem, and later work by Hjorth, Farah and Thomas, implies that if a group is not type I, then it is quite hard to classify the irreducible unitary representations.
In this talk I will give an overview of the descriptive set-theoretic perspective on the classification of irreducible representations, and I will discuss a new proof of Thoma's theorem due to F.E. Tonti and the speaker.
We show that for every ordinal \(\alpha \in [1, \omega_1)\), there is a closed set \(F \subset 2^\omega \times \omega^\omega\) such that for every \(x \in 2^\omega\), the section \(\{y\in \omega^\omega : (x,y) \in F\}\) is a two-point set and \(F\) cannot be covered by countably many graphs \(B(n) \subset 2^\omega \times \omega^\omega\) of functions of the variable \(x \in 2^\omega\) such that each \(B(n)\) is in the additive Borel class \(\mathbf\Sigma^0_\alpha\). This rules out the possibility to have a quantitative version of the Luzin-Novikov theorem. The construction is a modification of the method of Harrington who invented it to show that there exists a countable \(\Pi^0_1\) set in \(\omega^\omega\) containing a non-arithmetic singleton. By another application of the same method, we get closed sets excluding a quantitative version of the Saint Raymond theorem on Borel sets with \(\sigma\)-compact sections. (Joint work with P. Holický)
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, T(x), T^2(x), \ldots, 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, for pmp actions of finitely generated groups, where the averages are taken along set-theoretic (but backward) trees on the generating set. This strengthens Bufetov's theorem from 2000, which was the leading result in this vein. This is joint work with Jenna Zomback.
Beyond the Baire space, recursively presented metric spaces are structures which serve as a setting for effective descriptive set theory. Motivated by the classical distinction between a complete separable metric space and its corresponding Polish space topological structure, we will explore the notions and issues involved in moving from a recursively presented metric space to its effective Polish space structure. We will survey different approaches to these issues, in particular work by Moschovakis on recursive frames and work by Louveau on effective topology, and prove some original results which clarify some foundational problems in the area.
A locale is, informally, a topological space without an underlying set of points, with only an abstract lattice of "open sets". Various results in the literature suggest that locale theory behaves in many ways like a generalization of descriptive set theory with countability restrictions removed. This talk will introduce locale theory from a descriptive set-theoretic point of view, and survey some known and new results which are common to both contexts. In particular, we will introduce the "\(\infty\)-Borel hierarchy" of a locale, and sketch the existence of "\(\sigma\)-analytic, non-\(\infty\)-Borel sets".
The talk will be an outline of the book we published with Paul Larson recently. In particular, I will show how amalgamation problems in algebra naturally appear in consistency results for the choiceless set theory \(\mathsf{ZF} + \mathsf{DC}\), and how they can be stratified from a set-theoretic point of view.
Martin's conjecture is an attempt to make precise the idea that the only natural functions on the Turing degrees are the constant functions, the identity, and transfinite iterates of the Turing jump. The conjecture is typically divided into two parts. Very roughly, the first part states that every natural function on the Turing degrees is either eventually constant or eventually increasing and the second part states that the natural functions which are increasing form a well-order under eventual domination, where the successor operation in this well-order is the Turing jump.
In joint work with Benny Siskind, we prove part 1 of Martin's conjecture for a class of functions that we call measure-preserving. This has a couple of consequences. First, it allows us to connect part 1 of Martin's conjecture to the structure of ultrafilters on the Turing degrees. Second, we also show that every order-preserving function on the Turing degrees is either eventually constant or measure-preserving and therefore part 1 of Martin's conjecture holds for order-preserving functions. This complements a result of Slaman and Steel from the 1980s showing that part 2 of Martin's conjecture holds for order-preserving Borel functions.
A Cayley diagram for a Cayley graph \(G = \operatorname{Cay}(\Gamma, E)\) is an edge labelling of \(G\) with generators from \(E\) so that a path is labelled with a relation in \(\Gamma\) if and only if it is a cycle. I will show how \(\operatorname{Aut}(G)\)-f.i.i.d. Cayley diagrams can be used to lift \(\Gamma\)-f.i.i.d. solutions of local combinatorial problems to \(\operatorname{Aut}(G)\)-f.i.i.d. solutions. And, I will investigate which graphs admit \(\operatorname{Aut}(G)\)-f.i.i.d. Cayley diagrams, answering a question of Weilacher on approximate chromatic numbers in the process.
Although the Borel structure of \(\mathbb R/\mathbb Q\) is rather pathological in comparison to that of \(\mathbb R\), many theorems about the latter can be generalized to the former, and even to far more general quotient spaces. I will give a survey of several such theorems.
For a topological group \(G\), a \(G\)-flow is a continuous action of \(G\) on a compact Hausdorff space \(X\); we call \(X\) the phase space of the \(G\)-flow. A \(G\)-flow on \(X\) is minimal if \(X\) has no closed non-trivial invariant subset. The universal minimal \(G\)-flow, \(M(G)\), has every minimal \(G\)-flow as a quotient and it is unique up to isomorphism. We show that whenever we have a short exact sequence \[0\to K\to G\to H\to 0\] of topological groups with the image of \(K\) a compact normal subgroup of \(G\), then the phase space of \(M(G)\) is homeomorphic to the product of the phase space of \(M(H)\) with \(K\). For instance, if \(G\) is a Polish, non-Archimedean group, and the image of \(K\) is open in \(G\), then \(H\) is a countable discrete group. The phase space of \(M(H)\) is homeomorphic to \(\operatorname{Gl}(2^{2^{\aleph_0}})\), the Stone space of the completion of the free Boolean algebra on \(2^{\aleph_0}\) generators by Balcar-Błaszczyk and Glasner-Tsankov-Weiss-Zucker. Therefore, the phase space of \(M(G)\) is homeomorphic to \(K\times \operatorname{Gl}(2^{2^{\aleph_0}})\). When the sequence splits, that is, \(G\cong H\ltimes K\), then the homeomorphism witnesses an isomorphism of flows, recovering a result of Kechris and Sokić.
The Ki-Linton theorem asserts that the set of base \(b\) normal numbers is a \(\mathbf\Pi^0_3\)-complete set. The base \(b\) normal numbers can be viewed as the set of generic points for an associated dynamical system. This leads to the question of the complexity of the set of generic points for other numeration/dynamical systems, for example continued fractions, \(\beta\)-expansions, Lüroth expansions to name a few. We prove a general result which covers all of these cases, and involves a well-known property in dynamics, a form of the specification property. We then consider differences of these sets. Motivated by the descriptive set theory arguments, we are able to show that the set of continued fraction normal but not base \(b\) normal numbers is a complete \(D_2(\mathbf\Pi^0_3)\) set. Previously, the best known result was that this set was non-empty (due to Vandehey), and this assumed the generalized Riemann hypothesis. The first part of the work is joint with Airey, Kwietniak and Mance, and the second part with Mance and Vandehey.
This talk will compute the relations between the cardinality of some sets under determinacy. Woodin showed under \(\mathsf{ZF}\), dependent choice, and real determinacy that the set of countable sequences of countable ordinals does not inject into the set of \(\omega\)-sequences of countable ordinals and in fact does not even inject into the class of \(\omega\)-sequences of ordinals. This argument passes through a set called \(S_1\) and uses \(\mathsf{AD}^+\) techniques involving \(\infty\)-Borel codes, inner models of choice, and forcing arguments. In this talk, we will show a continuity result for functions from the set of sequences of countable ordinals of a fixed countable length into \(\omega_1\). This continuity result will be used to show in just \(\mathsf{AD}\) that the set of \(\omega\)-sequences of countable ordinals has strictly smaller cardinality than the set of countable-length sequences of countable ordinals. Then under \(\mathsf{AD}\) and dependent choice for the reals, this result along with category arguments, generic coding, and a bounding result of Steel will be used to show that the set of countable sequences of countable ordinals does not inject into the class of \(\omega\)-sequences of ordinals. These arguments are combinatorial and are more adaptable to the analogous questions for \(\omega_2\) and the odd projective ordinals. This is joint work with Stephen Jackson and Nam Trang.
A Polish module is a topological module whose underlying topology is Polish. In this talk, I will discuss some very recent work (joint with Forte Shinko) where we study when uncountable Polish modules continuously inject into one another and the pre-order induced by these injections. In particular we will show that, for a wide class of rings, there are countably many minimal elements in this pre-order. As an application, we will construct a countable family of uncountable abelian Polish groups, at least one of which embeds into any other uncountable abelian Polish group.
Topological dynamics of Polish groups has interesting aspects not present in dynamics of locally compact groups. For example, there exist Polish groups whose all continuous actions on compact spaces have fixed points. Groups of this type, called extremely amenable, were first constructed by Herer and Christensen using certain submeasures. Later, Gromov and Milman made a connection between extreme amenability and the concentration of measure phenomenon from probability theory.
I will describe the above developments. In this context, I will present a new concentration of measure theorem inspired by geometric ideas related to the Loomis-Whitney theorem. I will describe the dynamical consequences, in the spirit of Gromov and Milman, of our concentration of measure theorem. These consequences generalize the Herer-Christensen result mentioned above as well as related results of Glasner and Pestov. All this depends on a new geometric classification of submeasures, which I will outline.
This is a joint work with F. Martin Schneider.
We study the descriptive complexity of Borel binary relations, compared with the notion of continuous reducibility. In a first part, we present some important tools interesting for themselves. The second part is devoted to Borel equivalence relations. The last part, more recent, is about the generalization of some of the previous results to relations which are not necessarily equivalence relations. The case of graphs is particularily nice. Also, there is a surprising exception with the classes of rank two, related to topological Ramsey theory on the space of rational numbers.
We will discuss measurable cohomology of groups with Kazhdan's property (T). This will lead us to some cohomological characterizations of property (T), together with implications towards (the absence of) various lifting properties of these groups. In particular, we will construct "genuine" approximate homomorphisms into matrix algebras for a large class of property (T) groups. This is based on a recent joint work with Adrian Ioana and Matthew Wiersma.
A proper coloring of a graph is called equitable if every color class has (approximately) the same number of vertices. In the finite setting, the celebrated Hajnal-Szemerédi theorem establishes the existence of equitable \((d + 1)\)-colorings, where \(d\) is a bound on the vertex degrees. We discuss the existence of equitable \((d + 1)\)-colorings in the measure-theoretic and purely Borel contexts. Time permitting, we also discuss measure-theoretic analogs of recent work of Kostochka-Nakprasit on the existence of equitable \(d\)-colorings for graphs of low average degree. This is joint work with Anton Bernshteyn.