Search

We show that every $d$-regular bipartite Borel graph admits a Baire measurable $k$-regular spanning subgraph if and only if $d$ is odd or $k$ is even. This gives the first example of a locally checkable coloring problem which is known to have a Baire measurable solution on Borel graphs but not a computable solution on highly computable graphs. We also prove the analogous result in the measure setting for hyperfinite graphs.

Countable $\mathcal{L}$-structures $\mathcal{N}$ whose isomorphism class supports a permutation invariant probability measure in the logic action have been characterized by Ackerman-Freer-Patel to be precisely those $\mathcal{N}$ which have no algebraicity. Here we characterize those countable $\mathcal{L}$-structure $\mathcal{N}$ whose isomorphism class supports a quasi-invariant probability measure. These turn out to be precisely those $\mathcal{N}$ which are not "highly algebraic" -- we say that $\mathcal{N}$ is highly algebraic if outside of every finite $F$ there is some $b$ and a tuple $\bar{a}$ disjoint from $b$ so that $b$ has a finite orbit under the pointwise stabilizer of $\bar{a}$ in $\mathrm{Aut}(\mathcal{N})$. As a bi-product of our proof we show that whenever the isomorphism class of $\mathcal{N}$ admits a quasi-invariant measure, then it admits one with continuous Radon--Nikodym cocycles.

Extending a result of Christiansen, we prove that every mutli-graph $G=(V,E)$ admits a proper edge colouring $\phi:E\to \{1,2,\dots\}$ which is local, that is, $\phi(e)\le \max\{d(x)+\pi(x),d(y)+\pi(y)\}$ for every edge $e$ with end-points $x,y\in V$, where $d(z)$ (resp.\ $\pi(z)$) denotes the degree of a vertex $z$ (resp.\ the maximum edge multiplicity at $z$). This is derived from a local version of the Fan Equation., Comment: 10 pages, minor revision

We show that several new classes of groups are measure strongly treeable. In particular, finitely generated groups admitting planar Cayley graphs, elementarily free groups, and the group of isometries of the hyperbolic plane and all its closed subgroups. In higher dimensions, we also prove a dichotomy that the fundamental group of a closed aspherical 3-manifold is either amenable or has strong ergodic dimension 2. Our main technical tool is a method for finding measurable treeings of Borel planar graphs by constructing one-ended spanning subforests in their planar dual. Our techniques for constructing one-ended spanning subforests also give a complete classification of the locally finite pmp graphs which admit Borel a.e. one-ended spanning subforests., Comment: 42 pages, 2 x 2 figures

For an $r$-tuple $(\gamma_1,\ldots,\gamma_r)$ of special orthogonal $d\times d$ matrices, we say that the Euclidean $(d-1)$-dimensional sphere $S^{d-1}$ is $(\gamma_1,\ldots,\gamma_r)$-divisible if there is a subset $A\subseteq S^{d-1}$ such that its translations by the rotations $\gamma_1,\ldots,\gamma_r$ partition the sphere. Motivated by some old open questions of Mycielski and Wagon, we investigate the version of this notion where the set $A$ has to be measurable with respect to the spherical measure. Our main result shows that measurable divisibility is impossible for a "generic" (in various meanings) $r$-tuple of rotations. This is in stark contrast to the recent result of Conley, Marks and Unger which implies that, for every "generic" $r$-tuple, divisibility is possible with parts that have the property of Baire., Comment: 34 pages, minor changes, accepted by L'Enseignement Mathematique

A long standing open problem in the theory of hyperfinite equivalence relations asks if the orbit equivalence relation generated by a Borel action of a countable amenable group is hyperfinite. In this paper we prove that this question always has a positive answer when the acting group is polycyclic, and we obtain a positive answer for all free actions of a large class of groups including the lamplighter group and all virtually solvable groups having finite Pr\"ufer rank. This marks the first time that a group of exponential volume-growth has been verified to have this property. In obtaining this result we introduce a new tool for studying Borel equivalence relations by extending Gromov's notion of asymptotic dimension to the Borel setting. We show that countable Borel equivalence relations of finite Borel asymptotic dimension are hyperfinite, and more generally we prove under a mild compatibility assumption that increasing unions of such equivalence relations are hyperfinite. As part of our main theorem, we prove for a large class of solvable groups that all of their free Borel actions have finite Borel asymptotic dimension (and finite dynamic asymptotic dimension in the case of a continuous action on a zero-dimensional space). We also provide applications to Borel chromatic numbers, Borel and continuous Folner tilings, topological dynamics, and $C^*$-algebras., Comment: Corrected a typo in the proof of Theorem 4.8

We show that every basis for the countable Borel equivalence relations strictly above $\mathbb{E}_0$ under measure reducibility is uncountable, thereby ruling out natural generalizations of the Glimm-Effros dichotomy. We also push many known results concerning the abstract structure of the measure reducibility hierarchy to its base, using arguments substantially simpler than those previously employed.

We characterize the structural impediments to the existence of Borel perfect matchings for acyclic locally countable Borel graphs admitting a Borel selection of finitely many ends from their connected components. In particular, this yields the existence of Borel matchings for such graphs of degree at least three. As a corollary, it follows that acyclic locally countable Borel graphs of degree at least three generating $\mu$-hyperfinite equivalence relations admit $\mu$-measurable matchings. We establish the analogous result for Baire measurable matchings in the locally finite case, and provide a counterexample in the locally countable case.

Suppose that $X$ is a Polish space, $E$ is a countable Borel equivalence relation on $X$, and $\mu$ is an $E$-invariant Borel probability measure on $X$. We consider the circumstances under which for every countable non-abelian free group $\Gamma$, there is a Borel sequence $(\cdot_r)_{r \in \mathbb{R}}$ of free actions of $\Gamma$ on $X$, generating subequivalence relations $E_r$ of $E$ with respect to which $\mu$ is ergodic, with the further property that $(E_r)_{r \in \mathbb{R}}$ is an increasing sequence of relations which are pairwise incomparable under $\mu$-reducibility. In particular, we show that if $E$ satisfies a natural separability condition, then this is the case as long as there exists a free Borel action of a countable non-abelian free group on $X$, generating a subequivalence relation of $E$ with respect to which $\mu$ is ergodic.

Hajnal and Szemer\'{e}di proved that if $G$ is a finite graph with maximum degree $\Delta$, then for every integer $k \geqslant \Delta+1$, $G$ has a proper coloring with $k$ colors in which every two color classes differ in size at most by $1$; such colorings are called equitable. We obtain an analog of this result for infinite graphs in the Borel setting. Specifically, we show that if $G$ is an aperiodic Borel graph of finite maximum degree $\Delta$, then for each $k \geqslant \Delta + 1$, $G$ has a Borel proper $k$-coloring in which every two color classes are related by an element of the Borel full semigroup of $G$. In particular, such colorings are equitable with respect to every $G$-invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $\Delta$-colorings of graphs with small average degree. Namely, we prove that if $\Delta \geqslant 3$, $G$ does not contain a clique on $\Delta + 1$ vertices, and $\mu$ is an atomless $G$-invariant probability measure such that the average degree of $G$ with respect to $\mu$ is at most $\Delta/5$, then $G$ has a $\mu$-equitable $\Delta$-coloring. As steps towards the proof of this result, we establish measurable and list coloring extensions of a strengthening of Brooks's theorem due to Kostochka and Nakprasit., Comment: 32 pages, 4 figures

An abstract system of congruences describes a way of partitioning a space into finitely many pieces satisfying certain congruence relations. Examples of abstract systems of congruences include paradoxical decompositions and $n$-divisibility of actions. We consider the general question of when there are realizations of abstract systems of congruences satisfying various measurability constraints. We completely characterize which abstract systems of congruences can be realized by nonmeager Baire measurable pieces of the sphere under the action of rotations on the $2$-sphere. This answers a question of Wagon. We also construct Borel realizations of abstract systems of congruences for the action of $\mathsf{PSL}_2(\mathbb{Z})$ on $\mathsf{P}^1(\mathbb{R})$. The combinatorial underpinnings of our proof are certain types of decomposition of Borel graphs into paths. We also use these decompositions to obtain some results about measurable unfriendly colorings., Comment: minor corrections

In an unfriendly coloring of a graph the color of every node mismatches that of the majority of its neighbors. We show that every probability measure preserving Borel graph with finite average degree admits a Borel unfriendly coloring almost everywhere. We also show that every bounded degree Borel graph of subexponential growth admits a Borel unfriendly coloring., Comment: 6 pages

We show that a locally finite Borel graph is nonsmooth if and only if it admits marker sequences which are "far" from every point. Our proof uses the Galvin-Prikry theorem and the Glimm-Effros dichotomy.

We show that every probability-measure-preserving action of a countable amenable group G can be tiled, modulo a null set, using finitely many finite subsets of G ("shapes") with prescribed approximate invariance so that the collection of tiling centers for each shape is Borel. This is a dynamical version of the Downarowicz--Huczek--Zhang tiling theorem for countable amenable groups and strengthens the Ornstein--Weiss Rokhlin lemma. As an application we prove that, for every countably infinite amenable group G, the crossed product of a generic free minimal action of G on the Cantor set is Z-stable., Comment: Minor revisions. Final version

We study the relationship between hyperfiniteness and problems in Borel graph combinatorics by adapting game-theoretic techniques introduced by Marks to the hyperfinite setting. We compute the possible Borel chromatic numbers and edge chromatic numbers of bounded degree acyclic hyperfinite Borel graphs and use this to answer a question of Kechris and Marks about the relationship between Borel chromatic number and measure chromatic number. We also show that for every $d > 1$ there is a $d$-regular acyclic hyperfinite Borel bipartite graph with no Borel perfect matching. These techniques also give examples of hyperfinite bounded degree Borel graphs for which the Borel local lemma fails, in contrast to the recent results of Cs\'oka, Grabowski, M\'ath\'e, Pikhurko, and Tyros. Related to the Borel Ruziewicz problem, we show there is a continuous paradoxical action of $(\mathbb{Z}/2\mathbb{Z})^{*3}$ on a Polish space that admits a finitely additive invariant Borel probability measure, but admits no countably additive invariant Borel probability measure. In the context of studying ultrafilters on the quotient space of equivalence relations under $\mathrm{AD}$, we also construct an ultrafilter $U$ on the quotient of $E_0$ which has surprising complexity. In particular, Martin's measure is Rudin-Kiesler reducible to $U$. We end with a problem about whether every hyperfinite bounded degree Borel graph has a witness to its hyperfiniteness which is uniformly bounded below in size.

We generalize Brooks's theorem to show that if $G$ is a Borel graph on a standard Borel space $X$ of degree bounded by $d \geq 3$ which contains no $(d+1)$-cliques, then $G$ admits a $\mu$-measurable $d$-coloring with respect to any Borel probability measure $\mu$ on $X$, and a Baire measurable $d$-coloring with respect to any compatible Polish topology on $X$. The proof of this theorem uses a new technique for constructing one-ended spanning subforests of Borel graphs, as well as ideas from the study of list colorings. We apply the theorem to graphs arising from group actions to obtain factor of IID $d$-colorings of Cayley graphs of degree $d$, except in two exceptional cases., Comment: Minor corrections