It has been a long-lasting problem, posed by Weiss (1984), whether any Borel action of a countable amenable group on a standard Borel space gives rise to a hyperfinite Borel equivalence relation. This can be equivalently reformuated as whether countable amenable group action in a Borel way gives rise to the orbit equivalence relation being hyperfinite, liminf of a sequence of finite Borel equivalence relations, Borel embeddable into \(E_0\) or Borel reducible to \(E_0\). It is possible to consider these questions in a continuous setting, with the action being continuous, and a space being zero dimensional second countable Hausdorff, to see whether the induced orbit equivalence relation is continuously hyperfinite, liminf of \(G\)-clopen finite equivalence relations, continuously embeddable to \(E_0\) or continuously reducible to \(E_0\). We discuss that the one implies the other, but not necessarily the other way around. Also, we discuss the continuous analogue of the Borel asymptotic dimension, discuss its continuous embeddability and show that the shift action of \(G\) to \(2^G\) should have infinite continuous asymptotic dimension when \(G\) has an element of infinite order. Finally, we discuss the continuous embedding of a locally finite group into \(E_0\).
We consider the problem of finding a 2-regular subgraph of a given regular graph with no odd cycles. We show that this is always possible in the BP context. As a consequence, odd-regular bipartite Borel graphs on Polish spaces admit perfect matchings with the property of Baire, in contrast with recent examples of Kun in the measure-theoretic setting. Analogous results in the measure-theoretic context hold for hyperfinite graphs. This is joint work with Matt Bowen and Felix Weilacher, building upon prior joint work with Kechris and with Miller.
Analyzing when different generics for a given poset yield the same extension gives rise to countable Borel equivalence relations. We characterize when these relations are smooth. We also explore Prikry and Cohen forcing. This is joint work with Filippo Calderoni.
Several results regarding the topological and algebraic rigidity of maps and cocycles in the setting of Polish groups will be presented.Firstly, suppose \(G\) is a Polish group acting continuously on a Polish space \(X\), \(H\) is a Polish group and \(\psi: G \times X \to H\) is a cocycle that is continuous in the second variable. If \(\psi\) is either Baire measurable or is \(\lambda \times \mu\)-measurable with respect to Haar measure \(\lambda\) on \(G\) and a fully supported \(\sigma\)-finite Borel measure \(\mu\) on \(X\), then \(\psi\) is jointly continuous.Secondly, if \(\pi: G \to S\) is a map from a locally compact Polish group \(G\) into an abstract semigroup \(S\) and such that there is a conull subset \(\Omega \subseteq G \times G\) satisfying \[\pi(gf) = \pi(g) \cdot \pi(f)\] for all \((g, f) \in \Omega\), then there is a homomorphism \(\psi: G \to S\) agreeing with \(\pi\) almost everywhere. A similar statement holds for Baire category and further developments will be discussed.
A graphing of an equivalence relation \(E\) is a graph \(G\) whose connectivity equivalence relation is equal to \(E\). In previous joint work with Alekos Kechris and Patrick Lutz, we studied analytic equivalence relations which have Borel graphings. In this talk, we will discuss new results about when arithmetical equivalence relations have definable graphings which are lower down in the arithmetical hierarchy. In particular, we will see that for any computable relational language \(L\), computable isomorphism of \(L\)-structures presented on the natural numbers (a \(\Sigma^0_3\) equivalence relation) has a \(\Pi^0_2\) graphing. We will also prove a result on how to arithmetically construct a graphing of the Friedman-Stanley jump of \(E\) from a graphing of \(E\).
The talk explores connections between stellar moves on simplicial complexes (these are fundamental operations of combinatorial topology) and projective Fraïssé limits (this is a model theoretic construction with topological applications).We identify a class of simplicial maps that arise from the stellar moves of welding and subdividing. We call these maps weld-division maps. Our main theorem asserts that the category of weld-division maps fulfills the projective amalgamation property. This gives an example of an amalgamation class that substantially differs from known classes. As a consequence, we give a combinatorial description of the geometric realization of a simplicial complex and an example of a combinatorially defined projective Fraïssé class whose canonical quotient space has topological dimension strictly bigger than \(1\).The method of proof of the amalgamation theorem is new. It is not geometric or topological, but rather it consists of combinatorial calculations performed on finite sequences of finite sets. The set theoretic nature of the entries of the sequences is crucial to the arguments.
We introduce a natural notion of order-isomorphism between equivalence relations on \(\mathbb{R}\) and prove the following dichotomy theorem: if \(E = E_G\) is the orbit equivalence relation of a group \(G\) of orientation-preserving homeomorphisms of \(\mathbb{R}\) all of whose orbits are dense in \(\mathbb{R}\), then either \(E\) is isomorphic to the orbit equivalence relation of a group of translations, or \(E\) embeds an isomorphic copy of the tail-equivalence relation.We also discuss connections between this theorem and several related dichotomy theorems about linear orders due to Lindenbaum, Jullien, and Holland. In each of these theorems, the dichotomy in question distinguishes between linear orders that can in some sense be split into two copies of themselves and linear orders for which there is no such splitting.
The shift graph \(G_S\) on the infinite subsets of the naturals has been introduced by Kechris-Solecki-Todorcevic, alongside with the graph \(G_0\). Since then, it has become an important (and essentially unique) tool to establish complexity results concerning Borel coloring problems.In this talk, we show that much like \(G_0\), this graph is rather canonical. First, surprisingly, every acyclic Borel graph given by a function admits a Borel homomorphism to \(G_S\). Second, I will discuss that while a \(G_0\)-like dichotomy in the Borel context is not possible by complexity results, considering more relaxed versions of coloring could allow for positive results in the case of \(G_S\) and even general coloring problems. Joint work with Balazs Bursics and Anett Kocsis.
A locally checkable labeling problem (LCL) on a group \(\Gamma\) asks one to find a labeling of the Cayley graph of \(\Gamma\) satisfying a fixed, finite set of “local” constraints. Typical examples include proper coloring and perfect matching problems. We consider the existence of solutions to LCLs in the setting of descriptive set theory. For example, given a free action of \(\Gamma\) on a Polish space \(X\), we might be interested in solving a given LCL on each orbit in a continuous, Borel, measurable, etc. way.Motivated by a result of Bernshteyn's linking continuous combinatorics and distributed computing, we are especially interested in the difference between the Borel and continuous settings. Gao, Jackson, Krohne, and Seward showed that Free Borel actions of \(\mathbb{Z}^n\) always admit Borel 3-colorings (of the natural induced graph) but that 4 colors are needed for continuous colorings when \(n > 1\). Brandt et al. demonstrated a similar separation for \(\mathbb{F}_n\), the free group on \(n\) generators, when \(n > 1\).In an attempt to understand more finely the gap between Borel and continuous combinatorics, we consider the existence of Baire class \(m\) solutions to LCLs. For all \(n > 1\) and \(m \in \omega\), we extend Brandt et al.’s result by producing an LCL on \(\mathbb{F}_n\) which always admits Baire class \(m+1\) solutions, but not necessarily Baire class \(m\) solutions. There are only countably many LCLs, so it remains interesting question to determine the smallest \(\alpha < \omega_1\) for which the Baire class \(\alpha\) and Borel combinatorics of \(\mathbb{F}_n\) are identical.
In 2021, Todorčević and Vidnyánszky proved that the problem of deciding whether a locally finite Borel graph has a proper Borel 3-coloring is \(\mathbf{\Sigma}^1_2\)-complete. Building off of an argument of Thornton, we discuss how the polynomial-time gadget reductions used to establish NP-completeness can often be turned into Borel reductions to establish \(\mathbf{\Sigma}^1_2\)-completeness results in Borel combinatorics.
In this talk, we will discuss properties of sigma scattered linear orderings in the descriptive set theoretic world.
We show that Rufus Bowen’s Problem 32 on the classification of symbolic systems with the specification property does not admit a solution that would use concrete invariants. To this end, we construct a class of symbolic systems with the specification property and show that the conjugacy relation on this class is too complicated to admit such a classification. More generally, we gauge the complexity of the classification problem for symbolic systems with the specification property. Along the way, we also provide answers to two questions related to the classification of pointed systems with the specification property: to a question of Ding and Gu related to the complexity of the classification of pointed Cantor systems with the specification property and to a question of Bruin and Vejnar related to the complexity of the classification of pointed Hilbert cube systems with the specification property. This is joint work with Konrad Deka, Dominik Kwietniak and Marcin Sabok.
A result due to Schrittesser and the speaker states:
Theorem 1: If \(\Gamma\) is a somewhat "reasonable" class of subsets of Baire space which have the properties:
(1) All sets are completely Ramsey (i.e., Baire measurability w.r.t. the Ellentuck topology); and
(2) Uniformization (even just on Ramsey positive sets);
then there can't be any infinite maximal almost disjoint ("mad") families in \(\Gamma\).
The question arises if we can replace (1) by Laver measurability (in the sense of A. Miller), i.e.
(1') Every set in \(\Gamma\) either contains the set of branches through a Laver tree, or it avoids all branches through a Hechler tree.
In this talk, I will show this is not the case by constructing a \(\Pi^1_1\) infinite mad family in the Laver forcing extension of L (noting here that the class \(\Pi^1_1\) has uniformization, and by a result of A. Miller (1') holds in the in the Laver forcing extension of L).
The reason this is interesting (to me, at least) is that this shows that despite a number of similarities between generic reals for Laver and Ramsey measurability (and Laver and Mathias forcing), Laver can't replace Ramsey in the proof of Theorem 1.
This is joint work with David Schrittesser.
In joint work with Gianluca Basso, we explore the class of Polish groups whose universal minimal flows admit a comeager orbit. By work of Ben Yaacov, Melleray, and Tsankov, this class contains all Polish groups with metrizable universal minimal flow, and by an example of Kwiatkowska, this inclusion is strict. We isolate the correct generalization of this class of Polish groups to the class of all topological groups. We call these the topological groups with "tractable minimal dynamics (TMD)." One way of phrasing what makes this class "tractable" is an "abstract Kechris-Pestov-Todorcevic correspondence" which characterizes membership in TMD using a Ramsey-theoretic property of the group. In particular, this implies that TMD is absolute between models of set theory. We also state some conjectures to the effect that any topological group not in TMD has "wild" minimal dynamics.
Techniques in measurable combinatorics for solving graph labeling problems almost everywhere on a Borel graph are often adaptable to solve these problems on a comeager set. For example, Brandt, Chang, Grebík, Grunau, Rozhoň, and Vidnyánszky showed that every locally checkable labeling problem (LCL) admitting a mod-null solution on any \(d\)-regular acyclic Borel graph also admits a mod-meager solution on every such graph. Also, some results showing that measure-expansive pmp graphs have measurable perfect matchings have analogs in the Baire-measurable setting.Despite this, there is an LCL which always admits a measurable solution on any Schreier graph of a free Borel action of \(\mathbb{Z}^2\) but does not always admit a Baire measurable solution. This talk will discuss the methods used in these Baire measurable construction and obstruction results as well as the method of rectangular toast for constructing measurable labelings on grids. This includes joint work with Alexander Kastner as well as with Katalin Berlow, Anton Bernshteyn, and Felix Weilacher.
Let \(\Gamma\) be a compact Polish group of finite Lebesgue covering dimension. For a countably infinite subset \(S\subseteq \Gamma\), a domatic \(\aleph_0\)-partition (for its Schreier graph on \(\Gamma\)) is a partial function \(f: \Gamma\rightharpoonup\mathbb{N}\) such that for every \(x\in \Gamma\), one has \(f[S\cdot x]=\mathbb{N}\). We show that a continuous domatic \(\aleph_0\)-partition exists, if and only if a Baire measurable domatic \(\aleph_0\)-partition exists, if and only if the topological closure of \(S\) is uncountable. A Haar measurable domatic \(\aleph_0\)-partition exists for all choices of \(S\).We will talk about an application of this result to the theory of sum sets in \(\mathbb{R}^n\), and if time permits, some other examples of domatic partitions in the descriptive graph combinatorial setting. This work is based on an undergraduate thesis project under the supervision by Clinton Conley.
Ultraproducts of pmp group actions are a useful source of examples in measurable graph theory. In combinatorics, local-global limits are a notion of limit for sparse graphs. In some sense, these two notions of limits capture the same compactness phenomenon. In this talk, I'll generalize this theory to sparse hypergraphs and other structures, and I'll give some applications as time permits.
We define the \(\alpha\)-balanced Polish groups for \(\alpha < \omega_1\) and show that these form a stratification of the CLI Polish groups. Moreover, for every \(\alpha\), we give an example of an \(\alpha\)-balanced Polish group and a continuous action of it on a Polish space such that the resulting orbit equivalence relation is not Borel-reducible to any such action of a \(\beta\)-balanced Polish group for any \(\beta < \alpha\). Recall that the CLI Polish groups are those that have compatible complete left-invariant metrics, where a metric \(d\) is invariant if \(d(h, h') = d(gh, gh')\) for every \(g\), \(h\), and \(h'\). Our notion of \(\alpha\)-balanced is heavily inspired by a model-theoretic rank of Deissler, and another rank notion of Malicki. We also show that this class is in fact \(\Pi^1_1\)-complete, strengthening a result of Malicki.This is joint work with Aristotelis Panagiotopoulos.
In this talk, we present the classification of Baumslag-Solitar groups up to orbit equivalence and explore the techniques crucial to the proof. Of note are the usage of measure class preserving countable Borel equivalence relations of type III, i.e not preserving any equivalent measure.
There is an array of long-standing open problems in the theory of countable Borel equivalence relations (CBER), all of which state that the class of hyperfinite CBERs is nice in some way. For instance, the unresolved Union Problem asks whether the class of hyperfinite CBERs is closed under increasing unions, and in a different direction, it is also open whether the hyperfinite CBERs form a \(\mathbf{\Pi}^1_1\) set, which would be nicer than the naive complexity of \(\mathbf{\Sigma}^1_2\). There are many other such problems, and it is widely believed that if one of them is false, then most of the others will be false as well, although there is no formal statement to this effect. To this end, we show an implication between the two aforementioned problems: precisely, we show that if the Union Problem has a negative answer, then the Borel complexity of the class of hyperfinite CBERs is as high as possible, namely \(\mathbf{\Sigma}^1_2\)-complete. This is joint with Joshua Frisch and Zoltan Vidnyanszky.
A greedy algorithm argument demonstrates that any undirected graph of degree bounded by \(d\) has chromatic number at most \(d + 1\). This upper bound is sharp; the obvious obstructions to a smaller upper bound are odd cycles and complete graphs. In 1941, Brooks proved that these obstructions are the only ones: Any undirected graph of degree bounded by \(d\) not containing odd cycles or complete graphs admits a proper \(d\)-coloring. The determinacy argument of Marks demonstrates that there is no Borel analogue of Brooks's theorem. However, in 2016, Conley, Marks, and Tucker-Drob proved a measurable version of Brooks's theorem.
In the 1980s, combinatorialists introduced a coloring notion for directed graphs known as dicoloring. Work of Harutyunyan and Mohar resulted in a Brooks-like characterization of the directed graphs of maximum degree bounded by \(d\) that admit \(d\)-dicolorings. In this talk, we present and sketch a proof of a measurable version of this theorem. We explain also why the theorem has no Borel analogue.
It is a folklore principle of locally countable Borel combinatorics that most arguments amount to doing countable combinatorics "in a uniform Borel way". We prove a result making this precise, by showing that there is a dual equivalence of categories between countable Borel equivalence relations (CBERs) and countable \(\mathcal{L}_{\omega_1\omega}\) theories admitting a (one-sorted) interpretation of the distinguished theory of Lusin–Novikov uniformizing functions together with a separating family of unary predicates. This allows all combinatorial concepts on CBERs to be characterized in terms of definability in countable structures, modulo said distinguished theory which describes structure available "for free" on every CBER. If time permits, I will also discuss a generalization of this correspondence to locally countable Borel groupoids. This is joint work with Rishi Banerjee.
A Borel equivalence relation E on a standard Borel space is hyperfinite if it is the increasing union of Borel equivalence relations with finite classes. The hyperfinite Borel equivalence relations are the simplest nontrivial class of Borel equivalence relations, by the Glimm-Effros dichotomy of Harrington-Kechris-Louveau. Yet many questions about hyperfiniteness remain open. For example, it is an open problem of Weiss (1984) whether the orbit equivalence relation of a Borel action of a countable amenable group is hyperfinite.
Some researchers have hoped we can use soft tools from Borel graph combinatorics and metric geometry to attack this problem, rather than relying on a sophisticated understanding of the structure of Følner sets and their tilings which have been key to much partial progress on Weiss's question. Recently, Bernshteyn and Yu made a significant advance in this direction by showing that every graph of polynomial growth is hyperfinite. Their result parallels the 2002 theorem of Jackson-Kechris-Louveau that Borel actions of polynomial growth groups are hyperfinite. We extend Bernshteyn and Yu's result to show there is a constant \(0 < c < 1\) such that every graph of growth less than \(exp(n^c)\) is hyperfinite. This is joint work with Jan Grebík, Václav Rozhoň, and Forte Shinko.