Infinitesimal Containment and Sparse Factors of iid

Let Γ be a countable group with a Cayley graph G. Suppose we are running an independent identical probabilistic algorithm on each vertex (or each edge) and vertices are only allowed to communicate with their neighbors. The goal of this distributed algorithm could be, for example, to select a large independent set or find a small connected subgraph of G. In this talk we will consider the following general problem: what is the geometry of sparse subsets of G that can be distinguished by such a distributed algorithm? We call them sparse factor of iid subsets. Motivation for this question comes from measured group theory, especially the problem of estimating the cost of certain group actions. Although it sounds like computer science, our problem can be approached using dynamics of measure preserving action of Gamma.

We say that a measure preserving action X of a countable group Γ

is infinitesimally contained in Y if the statistics of the action of Γ

on small subsets of X can be projectively approximated inside Y.  It turns out that the Bernoulli shift [0,1]Γ

is always infinitesimally contained in the action of Γ

on itself. As a corollary we deduce that in Cayley graphs of linear groups, all sparse factor of iid subsets can be cut into finite pieces by deleting a small proportion of vertices. This forces strong geometric constraints on these subsets in e.g. lattices is semisimple Lie groups.