Negative Type and Bi-lipschitz Embeddings into Hilbert Space

The usual theory of negative type (and p -negative type) is heavily dependent on an embedding result of Schoenberg, which states that a metric space isometrically embeds in some Hilbert space if and only if it has 2-negative type. A generalisation of this embedding result to the setting of bi-lipschitz embeddings was given by Linial, London and Rabinovich. In this article we use this newer embedding result to define the concept of distorted p -negative type and extend much of the known theory of p -negative type to the setting of bi-lipschitz embeddings. In particular we show that a metric space (X,dX) ( X , d X ) has p -negative type with distortion C ( 0≤ p<∞ 0 ≤ p < ∞ , 1≤ C<∞ 1 ≤ C < ∞ ) if and only if (X,dXp/2) ( X , d X p / 2 ) admits a bi-lipschitz embedding into some Hilbert space with distortion at most C . Analogues of strict p -negative type and polygonal equalities in this new setting are given and systematically studied. Finally, we provide explicit examples of these concepts in the bi-lipschitz setting for the bipartite graphs Km,n K m , n .