Embeddings of Discrete Groups and the Speed of Random Walks

By Assaf Naor, Yuval Peres. 2007

77 citations recorded by the source corpus.

Let G be a group generated by a finite set S and equipped with the associated left-invariant word metric d G . For a Banach space X, let α * X (G) (respectively, α / # X (G)) be the supremum over all α ≥ 0 such that there exists a Lipschitz mapping (respectively, an equivariant mapping) f:G → X and c > 0 such that for all x, y ∈ G we have ‖ f(x) − f(y)‖ ≥ c · d G (x, y) α . In particular, the Hilbert compression exponent (respectively, the equivariant Hilbert compression exponent) of G is (respectively, ). We show that if X has modulus of smoothness of power type p, then . Here β * (G) is the largest β ≥ 0 for which there exists a set of generators S of G and c > 0, such that for all we have , where { W t } ∞ t=0 is the canonical simple random walk on the Cayley graph of G determined by S, starting at the identity element. This result is sharp when X = L p , generalizes a theorem of Guentner and Kaminker (20), and answers a question posed by Tessera (37). We also show that, if then . This improves the previous bound due to Stalder and Valette (36). We deduce that if we write and then and use this result to answer a question posed by Tessera in (37) on the relation between the Hilbert compression exponent and the isoperimetric profile of the balls in G. We also show that the cyclic lamplighter groups C 2 ≀ C n embed into L 1 with uniformly bounded distortion, answering a question posed by Lee, Naor, and Peres in (26). Finally, we use these results to show that edge Markov type need not imply Enflo type.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/cd78f27e21c9170dd8fbc92c057fe359b26f6c36

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Mathematical Physics

Citations in the corpus

Speed of random walks, isoperimetry and compression of finitely generated groups (2015, background): “1093/imrn/rnu075 [67] Naor, Assaf; Peres, Yuval, Embeddings of discrete groups and the speed of random walks, Int.”
Lp compression, traveling salesmen, and stable walks (2009, methodology): “Finally, it follows from [22, 47] that α ∗(C2 oFn) = α(C2 oFn) = 2 , where Fn is the free group on n ≥ 2 generators (the upper bound of 2 on α∗(C2 oFn) is due to [47] while the lower bound on α(C2 o Fn) is the key result of [22]).”