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.
Arens-Eells spaces (aka Lipschitz free spaces or transportation cost spaces) give rise to interesting examples of Banach spaces and provide analytic techniques within Banach space geometry. But they are also of importance as a tool for analysing objects outside Banach space theory using functional analytical techniques. I will present two such uses. The first is to abstract harmonic analysis where Arens-Eells spaces can be used to provide a very simple conceptual proof of a recent characterisation of amenability of topological groups due to F. M. Schneider and A. Thom. The second application is to the geometric study of topological groups, namely, to establish the Gromov correspondence between coarse equivalence and topological couplings in the widest possible setting.
In 2005, Kechris, Pestov and Todorčević exhibited a correspondence between combinatorial properties of structures and dynamical properties of their automorphism groups. In 2012, Angel, Kechris and Lyons used this correspondence to show the unique ergodicity of all the actions of some groups. In this talk, I will give an overview of the aforementioned results and discuss recent work generalizing results of Angel, Kechris and Lyons.
Cost is a $[1, \infty)$-valued measure-isomorphism invariant of aperiodic equivalence relations defined by Gilbert Levitt and heavily studied by Damien Gaboriau. For a large class of equivalence relations, including amenable, the cost is $1$. Yoshikata Kida and Robin Tucker-Drob recently defined the notion of an inner amenable equivalence relation as an analog of inner amenability in the setting of groups. We show inner amenable equivalence relations also have cost $1$. This is joint work with Robin Tucker-Drob.
We introduce a new class of jump operators on Borel equivalence relations, associated to countable groups. For each countable group $\Gamma$, we define the $\Gamma$-jump of an equivalence relation $E$ and produce an analysis of these jumps analogous to the situation of the Friedman-Stanley jump with respect to actions of $S_\infty$. In particular, we show that for many (but not all) groups the $\Gamma$-jump of $E$ is strictly above $E$ and iterates of the $\Gamma$-jump produce a hierarchy of equivalence relations cofinal in terms of potential Borel complexity. We also produce new examples of equivalence relations strictly between $E_0^\omega$ and $F_2$, and give an application to the complexity of the isomorphism problem for countable scattered linear orders. This is joint work with Sam Coskey.
I will discuss a measurable version of the Hall marriage theorem for actions of abelian groups. In particular, it implies that for free measure-preserving actions of such groups, if two equidistributed measurable sets are equidecomposable, then they are equidecomposable using measurable pieces. The latter generalizes a recent result of Grabowski, Máthé and Pikhurko on the measurable circle squaring and confirms a special case of a conjecture of Gardner. This is joint work with Tomasz Cieśla.
We construct Borel graphs which settle several questions in descriptive graph combinatorics. These include "Can the Baire measurable chromatic number of a locally finite Borel graph exceed the usual chromatic number by more than one?" and "Can marked groups with isomorphic Cayley graphs have Borel chromatic numbers for their shift graphs which differ by more than one?". As a result, we completely determine the set of pairs $(x,y)$ such that there exists a locally finite Borel graph with usual chromatic number $x$ and Baire measurable chromatic number $y$.
The von Neumann-Day problem has two parts: Is every amenable group elementary amenable? Is every group not containing a nonabelian free group (so-called small groups) amenable? Both problems have been settled in the negative. In this talk, I will present joint work with S. Kunnawalkam Elayavalli where we show that both problems have a generic negative solution. More specifically, we present natural Polish spaces of countable amenable groups and countable small groups and prove that the set of nonamenable small groups is comeager in the space of small groups and the set of non-elementary amenable groups is comeager in the space of amenable groups. We also discuss the analogous problem for groups satisfying laws and relate it to the well-known open question of whether or not every amenable group satisfying a nontrivial law is uniformly amenable. Time permitting, we will also discuss the question of when an amenable group can have the same first-order theory as a nonamenable group.
We prove simplicity for the automorphism groups of order and tournament expansions of homogeneous structures like the bounded Urysohn metric space, the random graph or more generally Fraïssé limits of free, transitive, non-trivial amalgamation classes. In particular, we will show that the automorphism group of the linearly ordered random graph is a simple group. This is joint with Filippo Calderoni and Katrin Tent.
A Borel equivalence relation that is induced by an action of a Polish group is essentially countable if it admits a countable complete Borel section. The notion of ($\sigma$-)lacunarity strengthens essential countability by requiring the complete section to be uniformly separated within each orbit. Kechris proved that every action of a locally compact Polish group is lacunary. More recently, B. Miller found a $G_0$-type dichotomy that characterizes $\sigma$-lacunarity for actions of TSI Polish groups. I will show that the notion of $\sigma$-lacunarity and essential countability coincide for Borel equivalence relations that are induced by actions of Polish groups. I will discuss some consequences for actions of TSI non-Archimedean Polish groups.
A Polish group $G$ is tame if for any continuous action of $G$, the corresponding orbit equivalence relation is Borel. Extending results of Solecki, Ding and Gao showed that if $G$ is a tame non-Archimedean abelian group, then in fact all actions of $G$ are potentially $\mathbf\Pi^0_6$, that is, they are Borel reducible to a $\mathbf\Pi^0_6$ orbit equivalence relation. They noted that all previously known examples of such actions were in fact potentially $\mathbf\Pi^0_3$, and conjectured that their upper bound could be improved to $\mathbf\Pi^0_3$. We refute this by finding an action of a tame non-Archimedean abelian group which is not potentially $\mathbf\Pi^0_5$. This is joint work with Shaun Allison.
I will show that Dilworth's theorem remains true in the Borel context: for a given natural number $n$, a Borel quasi-order $\le$ on a Polish space $X$ either contains an $(n+1)$-sized antichain, or $X$ can be covered by $n$ Borel chains. I will also discuss a generalization of a related theorem of Harrington, Marker, and Shelah, characterizing the existence of a perfect antichain.
Generalizing and simplifying recent work of Dobrinen, we show that if $\mathcal L$ is a finite binary relational language and $\mathcal F$ is a finite set of finite irreducible $\mathcal L$-structures, then the class $\mathcal K = \operatorname{Forb}(\mathcal F)$ has finite big Ramsey degrees.
A pointwise ergodic theorem for the action of a countable group Gamma on a probability space equates ergodicity of the action to its a.e. pointwise combinatorics. One result (joint work with Jon Boretsky) we will discuss is a short, combinatorial proof of the pointwise ergodic theorem for free, probability measure-preserving (pmp) actions of amenable groups along Tempelman Følner sequences, which is a slightly less general version of Lindenstrauss's celebrated theorem for tempered Følner sequences. In fact, we prove that such actions have a certain tiling property, which implies the pointwise ergodic theorem. Another result we will discuss is a similar tiling property in the quasi-pmp setting for the natural boundary actions of the free group on $n$ generators ($n < \infty$), which implies the corresponding pointwise ergodic theorem.
A well-known and long-standing open problem in the theory of Borel equivalence relations asks if the orbit equivalence relation generated by a Borel action of a countable amenable group is hyperfinite. Previous progress on this problem has been confined to groups possessing coarse Euclidean geometry and polynomial volume growth (ultimately leading to a positive answer for groups that are either virtually nilpotent or locally nilpotent). In this talk, I will discuss the coarse geometric notion of asymptotic dimension and its recently discovered applications to this problem. Relying upon the framework of asymptotic dimension, it is possible to both significantly simplify the proofs of prior results and uncover the first examples of solvable groups of exponential volume growth all of whose Borel actions generate hyperfinite equivalence relations. This is joint work with Clinton Conley, Steve Jackson, Andrew Marks, and Robin Tucker-Drob.
The Poisson boundary of a random walk is a measure of the space of asymptotic non-trivial events that can occur for a random walk on a group. In this talk, I will give an introduction to the notion of a Poisson boundary for a random walk on a countable group due to Furstenberg. I will define the Poisson boundary, explain the relationship between the Poisson boundary and harmonic functions, and explain the relationship between the Poisson boundary and amenability (due to Kaimanovich and Vershik) and the relationship between the Poisson boundary and the ICC property of groups. This is joint work with Yair Hartman, Omer Tamuz, and Pooya Vahidi Ferdowsi. No prior knowledge of random walks on groups will be assumed.
Descriptive combinatorics is the study of combinatorial problems (such as graph coloring) under additional topological or measure-theoretic regularity restrictions. It turns out that there is a close relationship between descriptive combinatorics and distributed computing, i.e., the area of computer science concerned with problems that can be solved efficiently by a decentralized network of processors. In this talk, I will outline this relationship and present a number of applications.
A big part of mathematical activity revolves around classification problems. However, not every classification problem has a satisfactory solution, and some classification problems are more complicated than others. Dynamical properties such as generic ergodicity and turbulence are crucial in the development of a rich complexity theory for classification problems. In this talk, we will review some of the existing anti-classification techniques and we will introduce a new obstruction for classification by orbit equivalence relations of TSI Polish groups; a topological group is TSI if it admits a compatible two-sided invariant metric. We will then show that the wreath product of any two non-compact subgroups of $S_\infty$ admits an action whose orbit equivalence relation is generically ergodic with respect to orbit equivalence relations of TSI group actions.
We review recent developments in which computability-theoretic dimensions of individual points have been used to answer open questions in classical geometric measure theory, questions whose statements do not involve computability theory or logic.
In this talk, we show that any generically $E_\infty$-ergodic equivalence relation cannot be Borel reducible to one that is induced by a Borel action of a non-Archimedean TSI Polish group (i.e. a closed subgroup of $S_\infty$ that has a two-sided invariant metric). We apply this fact to a family of equivalence relations recently studied by Clemens and Coskey, which they prove to be induced by actions of non-Archimedean CLI Polish groups. We also define a family of equivalence relations induced by Borel actions of a non-Archimedean TSI Polish group that are universal for their potential complexity class, mirroring results of Hjorth-Kechris-Louveau on actions of $S_\infty$. We apply this analysis to the theory of tame abelian groups, extending results of Solecki, Ding-Gao, and Malicki.
Given a countable group $\Gamma$, there is a compact space of subgroups $\operatorname{Sub}(\Gamma)$, which is equipped with the $\Gamma$-action via conjugation. We study the notion of weak containment on this space, namely when one subgroup is contained in the orbit closure of another, which is related to weak containment of quasi-regular unitary representations of $\Gamma$. In particular, we will consider necessary and sufficient conditions for the existence of dense orbits.
We show that the category of standard Borel spaces is the free or "universal" category equipped with some familiar set operations of countable arity (e.g., products) obeying some simple compatibility conditions (e.g., products distribute over disjoint unions). In this talk, we will discuss the precise formulation of this result, its connection with the amalgamation property for kappa-complete Boolean algebras, and its proof using methods from categorical logic.
By a flow, we mean a continuous action of a topological group $G$ on a compact Hausdorff space $X$. We refer to $X$ as the phase space of the flow. We are primarily interested in minimal flows, that is, flows with no non-trivial proper closed invariant subset. Among minimal flows, there exists a maximal one called the universal minimal flow, $M(G)$, which admits a continuous homomorphism onto every minimal flow. When $G$ is non-Archimedean, that is, it admits a neighbourhood basis of the identity of open subgroups, then $M(G)$ is $0$-dimensional. These are exactly groups of automorphisms of first-order structures with the topology of pointwise convergence. If $M(G)$ is $0$-dimensional, we can think dually in terms of its algebra of clopen subsets. We summarize which algebras are known to appear as phase spaces of universal minimal flows and we pose questions about the unknown.
It is a well-known open problem to determine if every group is sofic. A sofic group $G$ is said to be flexibly stable if every sofic approximation to $G$ can converted to a sequence of disjoint unions of Schreier graphs by modifying an asymptotically vanishing proportion of edges. We will discuss a joint result with Lewis Bowen that if $\operatorname{PSL}_d(\mathbb Z)$ is flexibly stable for some $d\ge 5$, then there exists a group which is not sofic.
Let $\Gamma$ be a countable group. The invariant random subgroup of a pmp action of $\Gamma$ on $X$ is the measure on the space of subgroups of $\Gamma$ obtained by pushing forward the measure on $X$ via the map sending $x$ to its stabilizer. A result of Elek states that if two pmp actions of $\Gamma$ have the same invariant random subgroup and one is hyperfinite, then they are strongly equivalent, so in particular they are both hyperfinite. We present a proof due to Giraud.
In this talk, we will go over the proof of the following theorem of Kathryn Mann: if $\operatorname{Homeo}(M)$ is the group of all homeomorphisms of a compact manifold $M$, endowed with the compact open topology, then every homomorphism from $\operatorname{Homeo}(M)$ to any separable topological group is necessarily continuous.
In this talk, we will go over the proof of the following theorem of Kathryn Mann: if $\operatorname{Homeo}(M)$ is the group of all homeomorphisms of a compact manifold $M$, endowed with the compact open topology, then every homomorphism from $\operatorname{Homeo}(M)$ to any separable topological group is necessarily continuous.
Given a countable group $\Gamma$, the outer automorphism group $\operatorname{Out}(\Gamma)$ is either countable or of cardinality continuum. A finer and more suitable notion is to consider the Borel complexity of $\operatorname{Out}(\Gamma)$ as a Borel equivalence relation. We show that in this context, $\operatorname{Out}(\Gamma)$ is of rather low complexity, namely that it is a hyperfinite Borel equivalence relation. In general, we show that for any Polish group $G$ and any countable normal subgroup $\Gamma$, the quotient group $G/\Gamma$ is hyperfinite. This is joint work with Joshua Frisch.