Metric Embeddings into L1 I'm really lost on how to go about proving a metric space can be embedded isometrically into L1. Like for example, how I can show that any metric space made of three points can be embedded into L1? 
I know that for a metric space to be embedded in L1, the following must hold:
$d(x,y) = \alpha$P($x$ and $y$ are separated by a partition). So for three points then, since there are three possible partitions (each point on its own), then the probability of $x$ and $y$ being separated is 2/3? 
Am I doing this right?
 A: When we think of a 3-point metric space, say $\{A,B,C\}$, the first picture that comes to mind is a triangle: pairwise distances are represented by the side lengths.  

But it's often more useful to represent such a space as vertices of a tripod. Specifically, we can draw a graph of the form shown below and assign length to each edge so that $|AB|$ is equal to the length of the shortest path from $A$ to $B$, etc. 

Indeed, we have the system of linear equations 
$$\begin{cases}
 a+b  = |AB| \\ 
 a+c  = |AC| \\ 
 b+c  = |BC| \\ 
 \end{cases}$$
with a unique solution 
$$\begin{cases} a = \frac{1}{2}(|AB|+|AC|-|BC|) \\
 b = \frac{1}{2}(|AB|+|BC|-|AC|) \\ 
 c = \frac{1}{2}(|AC|+|BC|-|AB|)  
\end{cases}$$
By the triangle inequality, the numbers $a,b,c$ are nonnegative (if a number is zero, the corresponding edge can be contracted to a point). 
To prove that there is an isometric embedding into $L^1$, assign 


*

*weight $a$ to the partition $\{A\}$, $\{B,C\}$  

*weight $b$ to the partition $\{B\}$, $\{A,C\}$

*weight $c$ to the partition $\{C\}$, $\{A,B\}$


and observe that this reproduces the given metric.
Generalization to trees
This proof immediately generalizes to any metric tree, that is, a graph without loops, in which every edge is given some length. The partitions are formed by removing an edge from the graph, and the weight assigned to it is the length of that graph. 
