Girth and Euclidean distortion / Random walks and Hilbert space compression- notes Probability, Geometry and Groups seminar, Toronto, 05.10.2012

Recall that for two metric spaces (X, d), Y, d ′ we say that a map f: X → Y is an embedding with distortion α if there exists a constant C> 0 such that: d(x, x ′ ) ≤ 1 C d ′ (f(x), f(x ′)) ≤ α d(x, x ′) for all x, x ′ ∈ X. The constant C represents a rescaling of the metric, so that simply rescaling all distances by a factor of C in X doesn’t incur any distortion, i.e. has α = 1. In particular for Y = ℓ 2 (with the standard norm, denoted by ‖ · ‖) we obtain the notion of a Euclidean embedding: f: X → ℓ 2 and the inequality: d(x, x ′ ) ≤ 1 C ‖f(x) − f(x ′) ‖ ≤ α d(x, x ′) The smallest α for which there exists an embedding into ℓ 2 with distortion α is called the Euclidean distortion of X and denoted by c2(X). We will prove the following bound for embeddings of regular graphs: Theorem 1.1 ([LMN02]). Let G be a finite d-regular graph, d ≥ 3, with girth g. Then the Euclidean distortion of G is Ω ( √ g). It is an open problem if this bound can be improved, for example to c2(G) = Ω(g). Note that for expanders on n vertices we have c2(G) = Ω(log n) and there exist expanders with girth Ω(log n), so at least in this case the bound is not tight. We will give a simple proof of this theorem employing the concept of the Markov type of a metric space. The paper [LMN02] contains also more refined results, using more involved techniques related to Poincaré-type inequalities on graphs. 1 Definition 1.2. We say that a metric space (X, d) has Markov type p if there exists a constant C> 0 such that for every reversible Markov Chain {Xn} ∞ n=0 on X, started in the stationary distribution, and every time T> 0 we have: E d(X0, XT) p ≥ C p T E d(X0, X1) p The best constant C that can be put on the right hand side is denoted by Mp(X) and we say that X has Markov type p with constant Mp(X). In other words, if a metric space has Markov type p, then any reversible random walk on this space will after time T be at a distance at most T 1/p away from its starting point. In general determining Markov type of a given metric space is difficult (REF-peresschramm-etal). However we will only need the following rather intuitive and easy to prove fact:

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.