Negative Type and Bi-lipschitz Embeddings into Hilbert Space

Abstract 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, dₗ) (X, d X) has p -negative type with distortion C (0 p 0 ≤ p ∞, 1 C 1 ≤ C ∞) if and only if (X, dₗ^p/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 K₌, ₍ K m, n.