Negative Type and Bi-lipschitz Embeddings into Hilbert Space

The usual theory of negative type (andp-negative type) is heavily dependent on anembedding result of Schoenberg, which states that a metric space isometrically embedsin some Hilbert space if and only if it has 2-negative type. A generalisation of thisembedding result to the setting of bi-lipschitz embeddings was given by Linial, Londonand Rabinovich. In this article we use this newer embedding result to define the conceptof distortedp-negative type and extend much of the known theory ofp-negative typeto the setting of bi-lipschitz embeddings. In particular we show that a metric space(X,dX)hasp-negative type with distortionC(0 <= p<infinity,1 <= C<infinity) if and onlyif(X,d(X)(p/2))admits a bi-lipschitz embedding into some Hilbert space with distortionat mostC. Analogues of strictp-negative type and polygonal equalities in this newsetting are given and systematically studied. Finally, we provide explicit examples ofthese concepts in the bi-lipschitz setting for the bipartite graphsKm,n