Search for: All records

We investigate when a Borel graph admits a (Borel or measurable) orientation with outdegree bounded by k k for various cardinals k k . We show that for a probability measure preserving (p.m.p) graph G G , a measurable orientation can be found when k k is larger than the normalized cost of the restriction of G G to any positive measure subset. Using an idea of Conley and Tamuz, we can also find Borel orientations of graphs with subexponential growth; however, for every k k we also find graphs which admit measurable orientations with outdegree bounded by k k but no such Borel orientations. Finally, for special values of k k we bound the projective complexity of Borel k k -orientability for graphs and graphings of equivalence relations. It follows from these bounds that the set of equivalence relations admitting a Borel selector is Σ 2 1 \mathbf {\Sigma }_{2}^{1} in the codes, in stark contrast to the case of smooth relations. 

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