Embedding the diamond graph in L_p and dimension reduction in L₁

We show that any embedding of the level k diamond graph of Newman and Rabinovich [NR] into L_p, 1 < p ≤ 2, requires distortion at least √k(p - 1) + 1. An immediate corollary is that there exist arbitrarily large n-point sets X ⊆ L₁ such that any D-embedding of X into ℓ₁^d requires d ≥ n ^Ω(1/D2). This gives a simple proof of a recent result of Brinkman and Charikar [BrC] which settles the long standing question of whether there is an L₁ analogue of the Johnson-Lindenstrauss dimension reduction lemma [JL].