Search for: All records

Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue 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 \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings 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 $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 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 $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit. 

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.