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.
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.
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.