Coarse embeddability, L¹-compression and Percolations on General Graphs

We show that a locally finite, connected graph has a coarse embedding into a Hilbert space if and only if there exist bond percolations with arbitrarily large marginals and two-point function vanishing at infinity. We further show that the decay is stretched exponential with stretching exponent α∈[0,1] if and only if the L¹-compression exponent of the graph is at least α, leading to a probabilistic characterization of this exponent. These results are new even in the particular setting of Cayley graphs of finitely generated groups. The proofs build on a new probabilistic method introduced recently by the authors to study group-invariant percolation on Cayley graphs [24,25], which is now extended to the general, non-symmetric situation of graphs to study their coarse embeddability and compression exponents.