This work is motivated by the Lecomte-Zeleny result giving a level by level version of the Kechris-Solecki-Todorcevic G0-dichotomy, proved for the first three levels. We present a new approach, based on forcing, allowing to prove a general level by level weak form of this dichotomy. It also gives a new proof of the (strong) dichotomy at the level three. If time permits, another new proof of the latter result, in terms of representation of Borel sets in the sense of Debs-Saint Raymond, will be described. Our forcing method also allows to recover other results from the field, like the Matrai theorem relating descriptive complexity and Baire category, and a complexity result about filters and ideals due to Debs and Saint Raymond. This is joint work with Greenberg, Turetsky and Zeleny.
The famous 4-color theorem says you only need 4 colors to color the countries on a planar map without giving neighbors the same color. We can ask local versions of these problems– What if each country chooses its color independently after talking to its neighbors? What if the map represents a torus and only looks planar close up? What if we want to define a coloring of an infinite graph without the axiom of choice?We will explore these questions for random maps related to percolation using factor of iid processes as a model for local algorithms. This talk is partly based on joint work done with Justin Hsu and Daniel Sium as part of CMU's SEMS program.
The back-and-forth relations, arising from the Ehrenfeucht-Fraisse games, are a central tool of countable structure theory. Each play of the Ehrenfeucht-Fraisse games takes two quantifiers, a universal quantifier and an existential quantifier, and so defining back-and-forth equivalence at the nth level takes 2n alternations of quantifiers. We will consider several situations in which this upper bound is sharp, and see how understanding this phenomenon has interesting applications, e.g., to degree spectra and to continuous reducibility between isomorphism equivalence relations.
We exhibit a geometric morphism from the Grothendieck topos representing the Solovay model to the κ-pyknotic sets of Barwick--Haine and Clausen--Scholze. We then use the properties of this morphism and automatic continuity in the Solovay model to outline a proof of Clausen--Scholze's resolution of the Whitehead problem for discrete condensed abelian groups. Based on joint work with Dianthe Basak.
The dichromatic number of a directed graph, a directed analogue of the chromatic number introduced by Neumann-Lara, is the minimum number of acyclic sets needed to partition its vertex set. Bokal et al. showed that deciding whether a finite digraph has dichromatic number at most 2 is NP-complete, in contrast with the undirected case where NP-completeness begins at 3 colors. In the Borel setting, the complexity landscape for chromatic numbers is well understood: the G0-dichotomy of Kechris, Solecki, and Todorčević provides a one-element basis at the countable/uncountable threshold, the L0-dichotomy of Carroy, Miller, Schrittesser, and Vidnyánszky does the same at the 2-/3-color threshold, and Todorčević and Vidnyánszky showed that no basis can exist at any higher finite threshold. For the dichromatic number, Raghavan and Xiao recently established a continuum-size basis at the countable/uncountable threshold. We complete the picture at finite thresholds: the set of Borel digraphs admitting a Borel 2-dicoloring is \(\mathbf{\Sigma}^1_2\)-complete, and consequently no countable basis exists for Borel digraphs of dichromatic number at least 3. Combined with a simple reduction from undirected to directed coloring, this settles the question for all finite thresholds of both the Borel chromatic and dichromatic numbers. The proof adapts the classical NP-completeness reduction to the Borel setting using Thornton's coding framework. We also discuss several open problems, including questions about bounded width CSPs and measurable arboricity.
Much of the current theory of orbit equivalence for minimal actions of abelian groups on the Cantor space is based on absorption theorems - roughly speaking, theorems that state that a "small" extension of a given equivalence relation is isomorphic to the original equivalence relation. I will describe a statement equivalent to the strongest known absorption theorem, which is due to Matui (building on work of Giordano, Putnam, and Skau), and try to give intuition for a relatively elementary proof of that statement by working out a particular case. In particular, I intend to explain why, if g is a minimal homeomorphism of the Cantor space, then the equivalence relation obtained by gluing two g-orbits (and leaving all other orbits unchanged) is isomorphic to the equivalence relation induced by g.
We study the complexity of locally checkable labeling problems on Borel graphs induced by actions of \(\mathbb{Z}^n\). Our results separate various complexity classes that were not previously known to be distinct and provide counterexamples to a number of natural conjectures in the field. In particular, we discuss a problem that has a factor-of-i.i.d. solution but no finitary factor-of-i.i.d. solution. We also expl as a cain how this problem servesounterexample to the shift being universal in the Baire measurable setting: it has a solution mod meager on the shift action, but not on all actions. This is joint work with Bernshteyn, Lyons, and Weilacher.
We show that a closed disk and square with the same area are equidecomposible with \(G_\delta\) pieces. A simple argument implies that the pieces are also \(F_\sigma\). Indeed the argument takes advantage of closure properties of the class of sets that are both \(G_\delta\) and \(F_\sigma\). More generally, we show that if A and B have the same positive Lebesgue measure and small boundary, then they are equidecomposible with pieces that are countable unions of finite Boolean combinations of translates of A, B and open sets. This is joint work with Narmada Varadarajan and Felix Weilacher.
We consider questions concerning what types of structures can be put in a continuous way on the free actions of Z^n. In particular we consider structures which on each class are finite unions of lines or trees. This is closely related to the continuous automorphism problem which asks on which invariant sets is there a continuous automorphism generating the equivalence relations. The main technical point is a new way of using certain hyperaperiodic elements to get results about continuous structurings. We apply this method to get results about linings, treeings, and some results about the automorphism problem. Parts of the work are joint with C. Olsen and parts with M. Kang.
We'll discuss recent joint work with Iian Smythe on the subject of this talk's title. We intend to focus on the classification of hyperbolic n-manifolds up to isometry -- or, equivalently, of discrete subgroups of Isom(H^n) up to conjugacy. We will not, though, presume any deep familiarity with hyperbolic geometry; efficiently building the relevant intuitions for this area is in fact among this talk's main aims.
In classical spectral graph theory, one associates to finite graphs Hermitian matrices, such as the adjacency matrix, that encode graphical information. The spectral properties of these matrices are then leveraged to analyze the combinatorial features - including vertex coloring, edge coloring, and matching - of the corresponding graphs. Analogously, one can associate bounded, self-adjoint operators, such as the adjacency operator, to pmp graphs of bounded degree. In this talk, we present new descriptive combinatorics results for pmp graphs that involve the application of spectral theory to their associated operators. In particular, we establish a spectral characterization of approximate measurable bipartiteness, as well as new bounds on the approximate measurable chromatic number. This is joint work with Pieter Spaas and Alexander Tenenbaum.
We explore to what extent classical descriptive set theory can be extended to nonseparable complete metric spaces. We concentrate on spaces whose weight is a singular cardinal of countable cofinality, and we show that, somewhat surprisingly, one can obtain a very rich theory. We also briefly discuss significant connections of such theory with very large cardinals, like Woodin's I0. This is joint work with Vincenzo Dimonte.
In a 2012 research note, Fokina, Friedman, Koerwien and Nies (hereafter abbreviated FFKN) considered metric spaces as classical model-theoretic structures in a signature that has countable many binary relation used to express whether the distance between a given pair is less than or greater than a given rational. Then they considered the Scott analysis and Scott rank of metric spaces. One of the main questions asked by FFKN was if the Scott rank of a complete, separable metric space is countable. In this talk, I will present an example of a complete, separable metric space which has Scott rank exactly \(\omega_1\). It was known, through work of Doucha, that the Scott rank can be at most \(\omega_1\), but it was not known if rank \(\omega_1\) could be attained. The proof that rank \(\omega_1\) is attained for the example given is interesting in that it uses a fair amount of moderately "serious" set theory. In particular, the proof relies on an idea which is similar in spirit to Stern's absoluteness and cardinality bounds for "virtual" Borel sets (i.e. Borel sets that exist in forcing extensions), and makes use of iterated powersets of \(\omega\), iterated through the countable ordinals.
The goal of this talk is to introduce a notion of hyperfiniteness for Borel partial orders, which was recently defined by Matthew Harrison-Trainor and myself as part of ongoing work. We were motivated to formulate this definition by a question about Turing reducibility. In particular, it turned out that this question is essentially equivalent to asking whether strict Turing reducibility is hyperfinite. I will introduce our notion of hyperfiniteness, discuss some of its basic properties, and then explain a general criterion which implies that a Borel partial order is not hyperfinite. Along the way, I will explain the answer to the question about Turing reducibility that was our original motivation for this work. I will also mention some open questions about hyperfinite Borel partial orders.
It is often possible to parametrize a given class of dynamical systems by elements of a Polish space and then it becomes natural to ask what properties hold "generically", i.e., on a comeager set of systems. The most extreme situation is when there is a single comeager isomorphism class: that is, the generic properties are captured by a single system. This does not usually happen in ergodic theory but, somewhat surprisingly and to an extent that is still not understood, this phenomenon does occur in zero-dimensional topological dynamics. For example, it is a result of Kechris and Rosendal that there is a generic action of \(\mathbb{Z}\) on the Cantor space and of Kwiatkowska that there is such a generic action of the free group \(F_n\). These actions are quite degenerate from dynamical point of view: for example, they cannot be topologically transitive. In this work, we are interested in minimal dynamical systems and show that there is a generic minimal action of \(F_n\) and also a generic minimal action of \(F_n\) that preserves a probability measure, and we identify these two actions. The tools we use come from symbolic dynamics. We also develop a model-theoretic framework to study this and related questions. This is joint work with Michal Doucha and Julien Melleray.
In joint work with Luca Motto Ros we prove that under analytic determinacy there exists an analytic relation that is not class-wise Borel embeddable into any orbit equivalence relation. The result builds on an unpublished result of Becker from 2001 and aims at better understanding the difference between idealistic and orbit equivalence relations. We will discuss how our result is motivated by other open questions in descriptive set theory and the \(E_1\) dichotomy conjecture.
I will present the notion of hyper-u-amenability for countable Borel equivalence relations, a property that implies 1-amenability and which is automatic for orbit equivalence relations of continuous amenable actions on sigma-compact Polish spaces, and for orbit equivalence relations of Borel actions of amenable groups. I will then show that hyper-u-amenable, treeable countable Borel equivalence relations are hyperfinite. As corollaries, I will show that, for orbit equivalence relations of free continuous actions of free groups on sigma-compact spaces, measure-hyperfiniteness implies hyperfiniteness, and that the orbit equivalence relation of a Borel action by an amenable group is hyperfinite, if treeable. The material presented is part of a joint work with Petr Naryshkin.
We study measure-class-preserving (mcp) equivalence relations and seek criteria for their (non)amenability. Such criteria are well established for probability-measure-preserving (pmp) equivalence relations, where tools like cost and \(\ell^2\)-Betti numbers are available. However, in the mcp setting, these tools are absent and much less is known. We discuss a recently developed structure theory for mcp equivalence relations, including a precise characterization of amenability for treed mcp equivalence relations in terms of the interplay between the geometry of the trees and the Radon–Nikodym cocycle. This generalizes Adams’ dichotomy to the mcp setting and yields a complete description of the structure of amenable subrelations of treed equivalence relations, as well as anti-treeability results. We also establish a Day–von Neumann-type result for multi-ended mcp graphs, generalizing a theorem of Gaboriau and Ghys. Joint work with Robin Tucker-Drob, and with Ruiyuan Chen and Grigory Terlov.
Let Γ be a countably infinite discrete group. A Γ-flow X (i.e., a nonempty compact Hausdorff space equipped with a continuous action of Γ) is called S-minimal for a subset S⊆Γ if the partial orbit S⋅x is dense for every point x∈X. (When S=Γ, we recover the usual notion of minimality.) Despite the simplicity of the definition, given a group Γ, finding an S-minimal dynamical system is typically quite difficult (in particular even when Γ is the free group and S is a subgroup it was not previously known). In this talk, I will discuss a very recent result on how to construct S-minimal systems for any countable collection of infinite subsets simultaneously. Although the problem is purely dynamical, the techniques make heavy use of recent ideas from descriptive set theory. Indeed, once the main result is established, we can return to derive some non-obvious, purely Borel, corollaries. This is joint work with Anton Bernshteyn.
In the probability measure preserving (p.m.p.) setup, a well-known consequence of Rokhlin's lemma is that any two aperiodic p.m.p. bijections are approximately conjugate, meaning that up to conjugacy, they only differ on sets of arbitrarily small measure. In the infinite measure-preserving (i.m.p.) setup, we will see why this is false and characterize approximate conjugacy for aperiodic i.m.p. bijections. This is joint work with Fabien Hoareau.
A characterisation of isometry topological groups of Polish ultrametric spaces is provided. This answers in the context of Polish spaces a problem of Krasner's. A finer analysis allows also to characterise isometry topological groups of subclasses of Polish ultrametric spaces, providing a solution to questions raised by Gao and Kechris. The groups obtained involve various kinds of generalised wreath products proposed in the literature by Hall, Holland, and Malicki. This is a joint work with A. Marcone and L. Motto Ros.
Given a class of groups, say the class of all countably infinite groups, it is natural to ask: what group properties are generic in the sense of Baire category in this class? For this question to make sense, we need a topology. In the case of countably infinite groups, a natural choice is the following: fix \(\mathbb{N}\) as a common universe and identify every group on \(\mathbb{N}\) with the group operation that defines it. These group operations form a Polish subspace in \(\mathbb{N}^{\mathbb{N}\times\mathbb{N}}\). I will talk about generic group properties in this setting, and, if time permits, I will also say a few words about other settings and generic properties in various classes of topological groups.
We show that there exists an equidecomposition between a closed disk and a closed square of the same area in \(\mathbb{R}^2\) by translations with algebraic irrational coordinates. Our proof uses a new method for bounding the discrepancy of product sets in the \(k\)-torus using only the Erdős–Turán inequality. This resolves a question of Laczkovich from 1990. We also obtain an improved upper bound on the number of pieces required to square the circle, by proving effective bounds on such discrepancy estimates for translations by certain algebraic irrational numbers. This builds on an idea of Frank Calegari for bounding certain sums of products of fractional parts of algebraic numbers, and some computer assistance. This is joint work with Spencer Unger.