
Multilabeled versions of Sperner's and Fan's lemmas and applications
We propose a general technique related to the polytopal Sperner lemma fo...
read it

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
read it

Continuous Tasks and the Chromatic Simplicial Approximation Theorem
The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy ...
read it

Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
In 1943, Hadwiger conjectured that every graph with no K_t minor is (t1...
read it

A topological dynamical system with two different positive sofic entropies
A sofic approximation to a countable group is a sequence of partial acti...
read it

The Post Correspondence Problem and equalisers for certain free group and monoid morphisms
A marked free monoid morphism is a morphism for which the image of each ...
read it

Resolvability on Continuous Alphabets
We characterize the resolvability region for a large class of pointtop...
read it
Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms
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 mid1970s. 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 TuckerDrob 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 zerodimensional Polish space. This fact is analogous to the theorem of Abért and Weiss for probability measurepreserving 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 Grebík, Jackson, Rozhoň, Seward, and Vidnyánszky). This establishes a formal correspondence between questions that have been studied independently in continuous combinatorics and in distributed computing.
READ FULL TEXT
Comments
There are no comments yet.