Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms

The probabilistic method is a technique for proving combina-torial existence results by means of showing that a randomly chosen object has the desired properties with positive proba-bility. A particularly powerful probabilistic tool is the Lovasz Local Lemma (the LLL for short), which was introduced by Erdos and Lovasz in the mid-1970s. Here we develop a version of the LLL that can be used to prove the existence of contin-uous colorings. We then give several applications in Borel and topological dynamics.center dot Seward and Tucker-Drob showed that every free Borel ac-tion I' r X of a countable group I' admits an equivariant Borel map pi: X -> Y to a free subshift Y subset of 2 Gamma. We give a new simple proof of this result.center dot We show that for a countable group I', Free(2 Gamma) is weakly contained, in the sense of Elek, in every free continuous ac-tion of I' on a zero-dimensional Polish space. This fact is analogous to the theorem of Abert and Weiss for probability measure-preserving actions and has a number of consequences in continuous combinatorics. In particular, we deduce that a coloring problem admits a continuous solution on Free(2 Gamma) if and only if it can be solved on finite subgraphs of the Cayley graph of I' by an efficient deterministic distributed algorithm (this fact was also proved independently and using different methods by Seward). This establishes a formal correspondence between questions that have been studied independently in continuous combinatorics and in distributed computing.(c) 2023 Elsevier Inc. All rights reserved.