Search

This paper is devoted to the study of analytic equivalence relations which are Borel graphable, i.e. which can be realized as the connectedness relation of a Borel graph. Our main focus is the question of which analytic equivalence relations are Borel graphable. First, we study an equivalence relation arising from the theory of countable admissible ordinals and show that it is Borel graphable if and only if there is a non-constructible real. As a corollary of the proof, we construct an analytic equivalence relation which is (provably in ZFC) not Borel graphable and an effectively analytic equivalence relation which is Borel graphable but not effectively Borel graphable. Next, we study analytic equivalence relations given by the isomorphism relation for some class of countable structures. We show that all such equivalence relations are Borel graphable, which implies that for every Borel action of $S_\infty$, the associated orbit equivalence relation is Borel graphable. This leads us to study the class of Polish groups whose Borel actions always give rise to Borel graphable orbit equivalence relations; we refer to such groups as graphic groups. We show that besides $S_\infty$, the class of graphic groups includes all connected Polish groups and is closed under countable products. We finish by studying structural properties of the class of Borel graphable analytic equivalence relations and by considering two variations on Borel graphability: a generalization with hypegraphs instead of graphs and an analogue of Borel graphability in the setting of computably enumerable equivalence relations., Comment: 60 pages

Standard results in descriptive set theory provide sufficient conditions for a set $P \subseteq \mathbb{N}^\mathbb{N} \times \mathbb{N}^\mathbb{N}$ to admit a Borel uniformization, namely, when $P$ has ''small'' sections or ''large'' sections. We consider an invariant analogue of these results: Given a Borel equivalence relation $E$ and an $E$-invariant set $P$ with ''small'' or ''large'' sections, does $P$ admit an $E$-invariant Borel uniformization? Given $E$, we show that every such $P$ admits an $E$-invariant Borel uniformization if and only if $E$ is smooth. We also compute the definable complexity of counterexamples in the case where $E$ is not smooth, using category, measure, and Ramsey-theoretic methods. We provide two new proofs of a dichotomy of Miller classifying the pairs $(E, P)$ such that $P$ admits an $E$-invariant uniformization, for $P$ with countable sections. In the process, we prove an $\aleph_0$-dimensional $(G_0, H_0)$ dichotomy, generalizing dichotomies of Miller and Lecomte. We also show that the set of pairs $(E, P)$ such that $P$ has ''large'' sections and admits an $E$-invariant Borel uniformization is $\boldsymbol{\Sigma^1_2}$-complete; in particular, there is no analog of Miller's dichotomy for $P$ with ''large'' sections. Finally, we consider a less strict notion of invariant uniformization, where we select a countable nonempty subset of each section instead of a single point., Comment: 41 pages

Nadkarni's Theorem asserts that for a countable Borel equivalence relation (CBER) exactly one of the following holds: (1) It has an invariant Borel probability measure or (2) it admits a Borel compression, i.e., a Borel injection that maps each equivalence class to a proper subset of it. We prove in this paper an effective version of Nadkarni's Theorem, which shows that if a CBER is effectively Borel, then either alternative (1) above holds or else it admits an effectively Borel compression. As a consequence if a CBER is effectively Borel and admits a Borel compression, then it actually admits an effectively Borel compression. We also prove an effective version of the ergodic decomposition theorem. Finally a counterexample is given to show that alternative (1) above does not admit an effective version., Comment: We have recently found out that the main results of the paper were included in the unpublished Caltech PhD thesis of Achim Ditzen, Definable Equivalence Relations on Polish Spaces (1992)

It is a long-standing open question whether every Polish group that is not locally compact admits a Borel action on a standard Borel space whose associated orbit equivalence relation is not essentially countable. We answer this question positively for the class of all Polish groups that embed in the isometry group of a locally compact metric space. This class contains all non-archimedean Polish groups, for which we provide an alternative proof based on a new criterion for non-essential countability. Finally, we provide the following variant of a theorem of Solecki: every infinite-dimensional Banach space has a continuous action whose orbit equivalence relation is Borel but not essentially countable., Comment: 18 pages

In this paper we develop a co-induction operation which transforms an invariant random subgroup of a group into an invariant random subgroup of a larger group. We use this operation to construct new continuum size families of non-atomic, weakly mixing invariant random subgroups of certain classes of wreath products, HNN-extensions and free products with amalgamation. By use of small cancellation theory, we also construct a new continuum size family of non-atomic invariant random subgroups of $\mathbb{F}_2$ which are all invariant and weakly mixing with respect to the action of $\text{Aut}(\mathbb{F}_2)$. Moreover, for amenable groups $\Gamma\leq \Delta$, we obtain that the standard co-induction operation from the space of weak equivalence classes of $\Gamma$ to the space of weak equivalence classes of $\Delta$ is continuous if and only if $[\Delta :\Gamma]<\infty$ or $\text{core}_\Delta(\Gamma)$ is trivial. For general groups we obtain that the co-induction operation is not continuous when $[\Delta:\Gamma]=\infty$. This answers a question raised by Burton and Kechris. Independently such an answer was also obtained, using a different method, by Bernshteyn.

We study the complexity of the isomorphism relation for various classes of closed subgroups of the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Polish spaces. For profinite, locally compact, and Roelcke precompact groups, we show that the complexity is the same as the one of countable graph isomorphism. For oligomorphic groups, we merely establish this as an upper bound, which is not sharp because the relation is Borel., Comment: arXiv admin note: text overlap with arXiv:1604.00609

We survey recent progress in the theory of weak containment of measure preserving group actions., Comment: Survey article. Final version - to appear in Ergodic Theory and Dynamical Systems

We show that weak containment of free ergodic measure-preserving actions of $\mathbf{F}_\infty$ is not equivalent to weak containment of the corresponding Koopman representations. This result is based on the construction of an invariant random subgroup of $\mathbf{F}_\infty$ which is supported on the maximal actions.

For a class $\mathcal K$ of countable relational structures, a countable Borel equivalence relation $E$ is said to be $\mathcal K$-structurable if there is a Borel way to put a structure in $\mathcal K$ on each $E$-equivalence class. We study in this paper the global structure of the classes of $\mathcal K$-structurable equivalence relations for various $\mathcal K$. We show that $\mathcal K$-structurability interacts well with several kinds of Borel homomorphisms and reductions commonly used in the classification of countable Borel equivalence relations. We consider the poset of classes of $\mathcal K$-structurable equivalence relations for various $\mathcal K$, under inclusion, and show that it is a distributive lattice; this implies that the Borel reducibility preordering among countable Borel equivalence relations contains a large sublattice. Finally, we consider the effect on $\mathcal K$-structurability of various model-theoretic properties of $\mathcal K$. In particular, we characterize the $\mathcal K$ such that every $\mathcal K$-structurable equivalence relation is smooth, answering a question of Marks., Comment: 77 pages; answered Remark 5.28 (Problem 9.2)

We show that the only random orderings of finite graphs that are invariant under isomorphism and induced subgraph are the uniform random orderings. We show how this implies the unique ergodicity of the automorphism group of the random graph. We give similar theorems for other structures, including, for example, metric spaces. These give the first examples of uniquely ergodic groups, other than compact groups and extremely amenable groups, after Glasner and Weiss's example of the group of all permutations of the integers. We also contrast these results to those for certain special classes of graphs and metric spaces in which such random orderings can be found that are not uniform., Comment: 39 pages

We study a positive-definite function associated to a measure-preserving equivalence relation on a standard probability space and use it to measure quantitatively the proximity of subequivalence relations. This is combined with a recent co-inducing construction of Epstein to produce new kinds of mixing actions of an arbitrary infinite discrete group and it is also used to show that orbit equivalence of free, measure preserving, mixing actions of non-amenable groups is unclassifiable in a strong sense. Finally, in the case of property (T) groups we discuss connections with invariant percolation on Cayley graphs and the calculation of costs.

We study topological properties of conjugacy classes in Polish groups, with emphasis on automorphism groups of homogeneous countable structures. We first consider the existence of dense conjugacy classes (the topological Rokhlin property). We then characterize when an automorphism group admits a comeager conjugacy class (answering a question of Truss) and apply this to show that the homeomorphism group of the Cantor space has a comeager conjugacy class (answering a question of Akin-Hurley-Kennedy). Finally, we study Polish groups that admit comeager conjugacy classes in any dimension (in which case the groups are said to admit ample generics). We show that Polish groups with ample generics have the small index property (generalizing results of Hodges-Hodkinson-Lascar-Shelah) and arbitrary homomorphisms from such groups into separable groups are automatically continuous. Moreover, in the case of oligomorphic permutation groups, they have uncountable cofinality and the Bergman property. These results in particular apply to automorphism groups of many $\omega$-stable, $\aleph_0$-categorical structures and of the random graph. In this connection, we also show that the infinite symmetric group $S_\infty$ has a unique non-trivial separable group topology. For several interesting groups we also establish Serre's properties (FH) and (FA).

We study in this paper some connections between the Fraisse theory of amalgamation classes and ultrahomogeneous structures, Ramsey theory, and topological dynamics of automorphism groups of countable structures., Comment: 73 pages, LaTeX 2e, to appear in Geom. Funct. Anal

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently., Comment: Association for Symbolic Logic

A Borel equivalence relation on a Polish space is said to be countable if all of its equivalence classes are countable. Standard examples of countable Borel equivalence relations (on the space of subsets of the integers) that occur in recursion theory are: recursive isomorphism, Turing equivalence, arithmetic equivalence, etc. There is a canonical hierarchy of complexity of countable Borel equivalence relations imposed by the notion of Borel reducibility. We will survey results and conjectures concerning the problem of identifying the place in this hierarchy of these equivalence relations from recursion theory and also discuss some of their implications., Comment: 12 pages

We show that a {\it Borel} action of a Polish group on a standard Borel space is Borel isomorphic to a {\it continuous} action of the group on a Polish space, and we apply this result to three aspects of the theory of Borel actions of Polish groups: universal actions, invariant probability measures, and the Topological Vaught Conjecture. We establish the existence of universal actions for any given Polish group, extending a result of Mackey and Varadarajan for the locally compact case. We prove an analog of Tarski's theorem on paradoxical decompositions by showing that the existence of an invariant Borel probability measure is equivalent to the nonexistence of paradoxical decompositions with countably many Borel pieces. We show that various natural versions of the Topological Vaught Conjecture are equivalent with each other and, in the case of the group of permutations of $\Bbb N$, with the model-theoretic Vaught Conjecture for infinitary logic; this depends on our identification of the universal action for that group., Comment: 8 pages