Geometry of Cuts and Metrics

M.M. Deza and M. Laurent,

Springer, 1997

• page 51, line 7 up: fiel' should be field'.

• page 85, line 3 of the proof of Theorem 6.3.6: replace $n$ by $N$ in $Q(-n,1,..,1)$.

• page 130, proposition 10.2.1: the argument for the implication (iii) ==> (ii) is not correct. It is indeed not clear why the inequality (10.2.4) (for any integer vector $b$ with $b^Te=0$) would imply the inequality (10.2.5) (for any positive semidefinite matrix $B$ with $Be=0$).

To correct Proposition 10.2.1, one must replace (iii) by:
(iii') For every positive semidefinite matrix $B$ with $Be=0$, the inequality (10.2.5) holds.

The implication (iii') ==> (ii) is now clear. For the implication (ii) ==> (iii'), use the fact that, if $D$ is a matrix of negative type and $B$ is a positive semidefinite matrix with $Be=0$, then $\sum_{i,j}B_{ij}D_{ij} \le 0$. To see it, write $B=bb^T + cc^T + ...$ for some vectors $b,c,...$ with $b^Te=c^Te=...=0$, and note that $\sum_{i,j}b_ib_jD_{ij} \le 0$ for any real vector $b$ with $b^Te=0$ (using a continuity argument).

• page 145, Example 11.1.8 (iv): ignore the second part of the last sentence, as this metric on 5 points is not split-free; indeed, the partition (1 5 , 2 3 4) gives a d-split.

• page 149, Theorem 11.1.21: in (iv) it suffices to cite the graphs $K_3$ and $C_4$, since the path metric of $K_3$ is a minor of the path metric of $K_{2,3}$.

Proof of Theorem 11.1.21: the current argument for the implications (iv)==>(ii) and (iii)==>(ii) is not correct. The proof goes as follows. Assume that (ii) does not hold. Suppose first that $d$ is not totally decomposable. Then, by Fact 11.1.13, the path metric of $K_{2,3}$) is a minor of $d$. Therefore, the path metric of $K_3$ is a minor of $d$, thus violating (iv). Condition (iii) is violated as well, since $d(K_3)$ is not $l_1^1$-embeddable and using Lemma 11.1.18. The rest of the proof is correct.

• page 159, the second summation symbol is missing in the displayed inequality; it should be the summation over $i=1$ to $n$ of the $p$th power of the $l_p$-norms of the $u_i$'s.

• page 214, Proposition 14.4.7: In the last sentence the upper bound should read: $(\rho(L))^2 \le 4/3 max(r^2,R^2)$.

• page 422, lines -14 and -17, replace twice integral' by 0/1-valued'. Thus it should read: "On the other hand, it is easy to check that the only 0/1-valued points of $MET_n$ are the multicut semimetrics. ... Therefore, the only 0/1-valued points of $MET_n$ ..."

Thanks in advance for mailing me further corrections.