On embedding expanders into ? p spaces

In this note we show that the minimum distortion required to embed alln-point metric spaces into the Banach space ℓ _p is between (c ₁/p) logn and (c ₂/p) logn, wherec ₂>c ₁>0 are absolute constants and 1≤p<logn. The lower bound is obtained by a generalization of a method of Linial et al. LLR95], by showing that constant-degree expanders (considered as metric spaces) cannot be embedded any better. Research supported by Czech Republic Grant GAČR 201/94/2167 and Charles University grants No. 351 and 361.