Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic

3 Further, we will also give an alternative proof for lower bounding the distortion when probabilistically embedding expander graphs into tree metrics. In addition, we also generalize this lower bound to the case when expander graphs probabilistically embed into graphs of constant characteristic. 1 Introduction The subject of graph embeddings deals with representing a finite point set in a metric space by points in another target metric space in such a way that the distances only increase, but not by too much. Once a given metric space can be approximately embedded into a metric space that is easier to deal with, one might get approximate solutions to problems which appeared to be hard to deal with in the original metric space. For a nice introduction to to this area refer to [7], [6] and [1]. This approach has been successfully adopted in several problems. One example would be for clustering points: here, one could embed the points at hand into some metric space such as the `2-space and try geometric algorithms that are already well known. Another example is bandwidth approximation. The first non-trivial approximation algorithm for bandwidth approximation was given in [9] using a generalization of the embeddings which form the subject of this paper. Bartal in [2] gave an algorithm to probabilistically approximate arbitrar