The following typos/little errors have been reported by now:
----------------------------------------
In subsection 5.3, two lines below Equation (10), I wrote:
Observe that H'H = I. Instead it should be:
Observe that H' D H = I.
(Thanks to Tian Xia, Institute of Computing Technology, Chinese
Academy of Sciences for pointing it out. )
----------------------------------------
Section 5.4, where I discuss the cockroach graph I wrote:
Obviously, the ideal RatioCut for k = 2 just cuts the ladder by a
vertical cut such that
A = {v_1, . . . , v_k, v)_{2k+1}, . . . , v_{3k}} and
\bar{A} = {v_{k+1},. . . , v_{2k}, v_{3k+1}, . . . , v_{4k}}.
Really, one should never write "obviously". Because, obviously what I
wrote in this sentence is wrong, as has been pointed out to me by
Jan-Georg Smaus. The cut which only separates one antenna from the rest
of the graph is even better than the vertical cut described above:
B = {v_1, ...., v_k},
\bar{B} = {v_{k+1}, ..., v_{4k} }.
Then:
cut(B, \bar{B}) = 1,
|B|=k, |\bar{B}| = 3k,
RatioCut(B, \bar{B}) = 1 ( 1/k + 1/(3k) ) = 4/3 k
while the vertical cut has a bigger ratio cut of
RatioCut(A, \bar{A}) = 2 ( 1/ (2k) + 1/(2k) ) = 2 k
----------------------------------------
In Section 5.1. I refer to Section 5.5.2 of Lütkepohl (1997), but the
reference should be to Section 5.2.2 instead (pointed out by Rene
Ciak).