Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms

• Published in: Advances in mathematics (New York. 1965) 2023-02, Vol.415, p.108895, Article 108895
• Main Author: Bernshteyn, Anton
• Format: Article
• Language: English
• Subjects: Continuous combinatorics; LOCAL algorithms; Lovász Local Lemma; Weak containment
• ISSN: 0001-8708; 1090-2082
• DOI: 10.1016/j.aim.2023.108895

The probabilistic method is a technique for proving combinatorial existence results by means of showing that a randomly chosen object has the desired properties with positive probability. A particularly powerful probabilistic tool is the Lovász Local Lemma (the LLL for short), which was introduced by Erdős and Lovász in the mid-1970s. Here we develop a version of the LLL that can be used to prove the existence of continuous colorings. We then give several applications in Borel and topological dynamics.•Seward and Tucker-Drob showed that every free Borel action Γ↷X of a countable group Γ admits an equivariant Borel map π:X→Y to a free subshift Y⊂2Γ. We give a new simple proof of this result.•We show that for a countable group Γ, Free(2Γ) is weakly contained, in the sense of Elek, in every free continuous action of Γ on a zero-dimensional Polish space. This fact is analogous to the theorem of Abért 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Γ) if and only if it can be solved on finite subgraphs of the Cayley graph of Γ 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.