List of Errata
Last modified: June
2
, 2007
If you detect
a misprint not in this list, please
use the
online form or just drop an
email.
Contributors names appear
in parenthesis.
I am grateful to all you!
"Line -
x" means x lines up from the bottom. Misleading errors inmathematics
are marked
boldface.
- page II (editorial):
"Lethuania" should be "Lithuania" (not my fault ...)
- page 3,
3rd paragraph: should be "Erdös"
- page 6: So as it is written the definition
of a cycle is not quite correct. Should be: "a cycle of length k+1 is a path
of length k whose first and last vertices are joined by an edge (not in the
path)" (C.J. Renteria)
- page 8, line -3: "f an"should
be "f is an" (R.
de Wolf)
- page 12, line -4: the sum should start at 0 instead of 1
(Tim van Erven)
- page 19, lines 8-11: A better
argument on why we may assume that both C0 and C1 are
non-empty could be the following: "If all strings in C have a
common prefix, then we can just remove it---the resulting code will havethesame
number of strings and the total length can only decrease." (C.J. Renteria)
- page 19, exercise
1.2: Replace "subsequent" by "consecutive"" (D. McLaury)
- page 21, Ex. 1.15: (n/k)^y should be (k/n)^y
(Guilherme Mota)
- page 21, Exercise
1.16: should be"Stirling
's" (A. Windsor)
- page 21, Exercise
1.19: the summing should start from i=0 instead
of i=1(T. Mielikäinen)
- page 22, Exercise
1.26: "newer" should be "never" (T. Tassa)
- page 25,
eqn. (2.5): here we assume |E|> an (for otherwise the result holds) (Tim van Erven)
- page 25,
line12: "Exercise 21.5" should be 21.4 (R. de Wolf)
- page 26, line
2: "x\in U" should be "x\in V_1"
- page 26,
line 6: "(n-(a-1))a" should be replaced by "na
"(V. Petrovic)
- page 29, Ex.2.3:
The condition "A\neq B" should be removed (Qiqi Yan)
- page 29,l ine
-1: "n-b+1" should be replaced by "n" (A. Utturwar)
- page 30, Ex.
2.7 (Hint): Vk should be Vr
- page 30, Ex.
2.8: "i_k" should be "i_s" (Tim van Erven)
- page 32, line
-8: Al should be Ak (QiGe)
- page 35, line -7: "s!" should be replaced
by "3!" (Wouter Koolen-Wijkstra)
- page 42,
line -6: (1-(n-k)/k)^2 should be (1+(n-k)/k)^2 (H. Hennings)
- page 45:
in Theorem 4.12 it is not said that labels of different edges must be different
(T.Hofmeister)
- page 48, line
7: "overcomming" should be "overcoming" (D. Gunderson, T. Hofmeister)
- page 49,3rd
sentence after the proofof Claim4.14: remove the "i.e." part or replace
"i.e., if" by "in particular," (T.Hofmeister). Replace "that" by "than"
(R.M. de Wolf)
- page 52, line
Ex.4.3: "subsequent" should be "consequtive" (Tim van Erven)
and the first set of pigeons should be (2i,2i-1) instead of (i,i+1) (Wouter Koolen-Wijkstra)
- page 58, line
13: "those of integers 1,2,...,r" should be "those integers 1,2,...,n",
that is, delete "of" and replace"r" by "n" (D. Krämer)
- page 59, line
-8: "incidence matrices"should be "adjacency matrices" (D. Krämer)
- page 63, lines
13-14: should be "from B0 to A0" (E. Weinreb)
- page 64, Ex.
5.5: It must be assumed that the sequence has a system of distinct
representatives (D. Zuckerman)
- page 65, line
3: "are hold"should be " are held" (T. Hofmeister)
- page 66, line
-20: "a family if" should be "a family is" (
E.Weinreb)
- page 68, line
12: "rectangles" should be "triangles"
- page 69, line
5: remove "of" in "Omega(n^2) of triangles" (R. deWolf)
- page 70, line 15: remove "of"
in "many of edges" (R.M. de Wolf)
- page 70, line -3: log|Delta|
should be log|{\cal G}|=|Delta| (R. de Wolf)
- page
71
, last paragraph in the proof of Theorem 6.6: Taking just a union of G1
and G2 is not a good idea: it may happen that the players
can (correctly) reject the resulting
graph G. To avoid this unpleasant situation, we should construct the graph
G as follows. Let x,y be the free edges of the
triangle t, and assume that x belongs to G1 (hence, y belongs to G2).Then
let G be the union of the the part of G1seen by
Alic ewith thepartof
G2 seen by Bob.
- page 71, line
8: replace "Untill" by "Until" (D. Sieling)
- page 71, line
16: "independent on" --> "independent of" (R. de Wolf)
- page 71, line
-10: Replace "aroses" by "arises" (Chien-ChungHuang)
- page 72, line
1: "blue" should be "black" (D. Krämer)
- page 72, Proposition
6.9: "colors" should be "properly colors" (S. Hada)
- page 74, Exercise
6.4: "Welsch"should be "Welsh"
- page 80, line
-7: replace "\Delta -system" by "weak\Delta-system"
(Ben Pak Ching Li)
- page 81, line
13: replace "petals" by "sets" (T. Hofmeister)
- page 82, line 1: (7.2) holds for a
proper subset of B_0 since |F(B_0)|={\emptyset}|=1
(R. de Wolf)
- page 82,
line -10: "at most s" should be just "s" (M.
Scheel)
- pages 85-86
(afterthe proof of Claim7.6): all three occurences of "F" should
bereplaced by "F_i" (S.Hada)
- page 86:
In exercise 7.2, the definition of F lacks the index i, should
read "for all i =1,...,s" (A. Zilberstein)
- page 87: Exercise
7.8 is from N. Alon, P. Pudlak: Constructive lower bounds for
off-diagonal Ramsey numbers, Israel Journ. of Math. 122 (2001), 243-251.
- page 102, line 6: one its --> one ofits
(R.M. de Wolf)
- page 104, line
5: "k=1" in the first summation should be "i=1" (
S.Hada)
- page 105, line
1: "more that" should be "more than" (S. Hada)
- page 105, line
11: Aia should be Ai,a
- page 109, Proposition 10.1: The proof
is somewhat unclear (Chien-Chung Huang, R. de Wolf).
Here is a more complete argument suggested by Tim van Erven and
Ronald de Wolf.
- page 110, Proposition 10.3: Claim (ii) holds
for all families, not just for anti-chains (Chien-Chung Huang)
- page 118, line 10: we can do this-->can
we do this (R. de Wolf)
- page 118,
lines -13 and-14: Should be "The length of a minterm is the
number n-|\rho^{-1}(*)| of assigned variables (
S.Hada)
-
page 118, line -3: replace "Bad"
by "Bad^{\ell}" (D. Sieling). Also there is an inconsistence with arguments
of "Bad": this set depends on three
parameters \ell, f and s. Correction: replace all occurences
of"Bad^{\ell}(s,t)" by "Bad^{\ell}(f,s)" (S. Hada)
-
page 119,
lines 8-9: replace "n-l+s" in the denominator by "n-l". Notet
hatthe estimate(10.4) in Switching Lemma is non-trivial only if the number
l of free variables is smaller than n/t, and hence,is
smaller than n/2 (the case t=2 istrivial).Thus,
we can safely take , say, \gamma=16 in the last
inequality on line 8. Actually, more precise calculations would yield almost
the same constant as in (10.4).
- page 125, line
4 in Sect. 10.6.2: "In the following three sections" should be "In this section"
- page 131, exercise
10.8: "bin(y)" should be "int(y)" (S. Hada)
- page 132, line
4: replace "{\calF}_v" by "{\cal D}"
- page 133
, line 9: "minimal number k" should be "maximal number k" (H. Prothmann)
- page 137, line 2: does --> do (R.
de Wolf)
- page 137, line
6: "This results" should be"This result" (T. Hofmeister)
- page 137, line
10: "will" and"later" is not good because , actually, Paley graph was
already used in the previous section (S.Hada)
- page 137, line
-9: "incidence matrix"should be "adjacency matrix" (H. Prothmann)
- page 139, line
13: "the set of" should be "the number of" (H. Prothmann)
- page 142, Ex.
11.9 (hint): the all-0 vector should be excluded (S. Bova)
- page 143, line
-8: the vector v=(v_1,...,v_n) has n coordinates,
not k (E. Weinreb)
- page 146, line
before Lemma 12.4: "Example 12.3" should be "Exercise 12.3"(D.
Sieling)
- page 148, line
-1: "edge (u,v) in E" should be "e=(u,v) in E" (S. Hada)
- page 149, line
-15: The upper bound on|W| must be n+1, not just
n (S. Hada)
- page 151, line 12: "options in Y"
--> "options within Y", i.e. no one changes his mind about
y<y' or y'<y for y,y' that are both
in Y (R. de Wolf)
- page 152,
line -9: Replace"max" by "min" in the definition of f(m,l)
(P.Rastas)
- page 155, line
-1: "Chap.14" should be "Chap. 15" (S. Hada)
- page 158, line
-19: Ignore this last sentence: in general, the transpose may change
the matrix--only its combinatorial properties remain the same
- page 159, line
-7: The reference to Blokhuis' result is missing: Blokhuis, A.
(1994):On the size of blocking sets in PG(2,p), Combinatorica 14:1,
111-114 (T. Mielikäinen)
- page 160, line
3 (definition of set J): add the condition that x \neq x'
(R. deWolf)
- page 160, line 10:
should be m^2 - 2(q+1)m + q^2 + q +1
(E. Dekel)
- page 161, line
-11: should be r=|D|k/v (T. Mielikäinen)
- page 163,line
-3: Brower --> Brouwer, Schrijev -->Schrijver. Same
on next page in Theorem 13.12, and in the Name Index. (R. de
Wolf)
- page 164, line 6: degree -->total
degree (R. de Wolf)
- page 164, line 14: d_i -->
d_j
-
page 164
, line -12: Ignore this sentence (this claim is still an open question).Hence,
the proof is only for a 2-dimensional affinespace
AG(2,q) over GF(q). It remains open whether a similar estimate holds also for
non-Desarguesian planes (F. Voloch)
-
page 170, a sentence before Prop.
14.2: "inequality" should be "equality"
- page 171, line
-8: the norms of u and v should be squared
- page 176, line
4 of Sec 14.3: remove "a" before "members"
(R. de Wolf)
- page 176, line
5 in Sect. 14.3: "know" should be "known" (T. Hofmeister)
- page 176, line
-3: "smallest" should be "largest" (Tim van Erven)
- page 177, line
19: 'no of which is zerro" should be "none of which is zero" (T. Hofmeister)
- page 177, line
-7: the summation should be over "i", not over " l
" (T.Mielikäinen)
- page 180, line
16: "leave them"should be "leave it" (T. Hofmeister)
- page 180, line
-7: " due Frankl" shouldbe "due to Frankl" (T. Hofmeister)
- page 181, line
5: "we look" should be "we look at" (A. Windsor)
- page 181, line
-12: the variables should be indexed from 0 to r, not from 1to r+1
(Qi Ge)
- page 182, line
-6: Justensen --> Justesen (R.M. de Wolf)
-
page 183, proof of Thm. 14.18:The
first two sentences are somewhat misleading. Should be: Take a maximal
set of vectors v1,...,vkin A such that the vector u
0=v1+...+vk cannot be represented as a sum of
fewer than k vectors from A (T.Mielikäinen)
- page 183, line
-13 (and the corresponding index entry): "MacWillams" should be "MacWilliams"
(T. Hofmeister)
-
page 185, lines 4-5:
Should be " we are charged for every bit of memory as well
as for the number of probes". The cases "1 bit + n probes" and"1
probe + n bits" both are trivial (J. Hünten)
-
page 189, line 17: The last sentence
of the hind should sound as follows: "Substitute the first set
I1 for the variables and observe that all but the
first function vanish." (S.Akbari)
- page 190, Exercise
14.26 (Hint): should be "for every v in spanA"
(T.Mielikäinen)
-
page 190, Exercise 14.28:
replace "," at the end of the last sentence by "."
- page 194: A better
lower bound \Omega(n^2/r)
on the rigidity of Hadamard matrices
was proved by Khasin and Razborov in 1998
(see Razborov's homepage); another proof of this bound using quantum arguments
was recently found by Ronald de Wolf (see his homepage); a few lines proof was then found
by Gatis Midrijanis (http://arxiv.org/abs/cs.CC/0506081)
- page 198, line
12: remove "is" (D. Sieling)
- page 202, line
18: replace "v"by "i"
-
page 203, line -2: The hint "apply
the pigeonhole principle" is somewhat misleading (S. Akbari) . I think
a more
direct argument works.
- page 204, line 12: holds -->hold
(R. de Wolf)
-
page 204, Exercise s15.6(ii) and
15.7: The reference to Alon at al (1988) is missing: Alon, N., Bergmann,
E.E., Coppersmith, D., and Odlyzko, A.M. (1988): Balancing sets of vectors,
IEEE Trans. Inf.Theory 34:1,128--130.
- page 207, line
14: the reference to A. Gal paper should be from 1998 and not from1992
(T.Tassa)
- page 208, line
15: It should be"m vertices" and not "n vertices"(T.Tassa)
- page 211,
first sentence in the proof of
Theorem 16.6: should be "A spans the all-1vector iff none of the odd
vectors is orthogonal to all rows of A"
- page 211, proof
of Theorem 16.6: in the proof we work entirely in the field F
2 (T.Tassa)
- page 215, line -12: remove "a contradiction"
(R. de Wolf)
- page 216, line
17 (point 4): change word order --> How much are... (R.de
Wolf)
- page 217,
line10 (Hint): "xj"
should be "yj"
- page 217
,line -10 (Hint): "Mb rb" should be
"M rb" (T. Mielikäinen)
- page 218, line
10: "span program"should be "dependency program" (T. Mielikäinen)
- page 222, line
16: replace "reflexive" by "symmetric"(D.Sieling)
- page 222, line
-2: replace \Omega by R (U. Leck)
- page 226, line
14: Am should be An
(Qi Ge)
- page 227, line
9: missing index in second summation, should be \alpha_i; also on line
14 replace n by
m (Qi Ge)
- page 233, line
3: "{0,1}^S" should be "{0,1}^k"
(Tim van Erven)
- page 236, Ex.
18.4: "l = 3k4kln n" can be replaced by "l = 2k4k
ln n" (A. Utturwar)
- page 238, line-4:
xi should be replaced by x1
(S. Bova)
- page 241, line 5: | F | * 2^(k-1),
should be: | F | * 2^(1-k) (S. Bova)
- page 253, line 9: the sum subscript,
v \in V, should be: v \in U (S. Bova)
- page 257
, line -18 (Thm. 20.11): " -2k " should be"
1/2k " (T. Mielikäinen)
- page 259,
Theorem20.15:
replace \sqrt(\logn)
by 2^{\sqrt(\logn)}
--> resp. corrections on page 348
(H.Klauck)
- page 262, Ex. 20.13 (hint):
"{0,1}^S" should be "{0,1}^k"
(Tim van Erven)
- page 267, line
21: The argument is a bit overloaded. The two events correspond to
two strings 110 and 001 out of eight. So, the probability that neither happens
is 6/8 = 3/4.
- page 268, line
-11 (proof of Theorem 21.7): add superscript -1 to the binomial
coefficient in the definition of p. Note also that
l and k
are fixed and n
is sufficiently large number.
- page 270, line
-2: N=|X| (T. Mielikäinen)
- page 277, equation (22.6): replace
"Y" by "T" (D. Sieling)
- page 288, line 9: add "the" before
"so-called" (R. deWolf)
- page 288, line
-15: ``maight" should be "might"(T. Hofmeister)
- page 288, line
-6: replace Hab by Haa
(D.Sieling)
- page 288, line
-9: P(X) is not a probability, it is just defined as this sum
(D. Sieling)
- page 289, line
1: "newer" should be"never"(T. Hofmeister)
- page 295, line 8: i \leq n,
should be: i \leq m (S. Bova)
- page 296, line 17: Prob(v=v),
should be: Prob(v=v_0) (S. Bova)
- page 297, line 7: comma should be after rather
than before "above" (R. de Wolf)
-
page 298, Ex. 24.2: 
the graph must be connected (Wouter Koolen-Wijkstra)
-
page 298, hint to Ex. 24.3:
replace "a=?" by "b=?"
-
page 301
, line -8: Inequality (1.3) does not help here (T. Mielikäinen).
Instead the following inequality 1-t >
e^{-t - t^2}, which holds for all 0< t\leq 1/2, should be used.
- page 308,
lines 17 and 20: should read "in order", not "in oder" (A. Zilberstein)
- page 308, line
24 should read "never", not" newer" (A. Zilberstein)
- page 308, line
-15: should read "mention" (A. Zilberstein)
- page 308, line -13: embracingly --> embarrassingly
(R. de Wolf)
-
page 308, line -8: "2^{-|\Omega|}"
should be "1/|\Omega|" (N. Schmitt)
-
page 312, line 16: "2^{-|\Omega|}"
should be again "1/|\Omega|=2-n " (N.
Schmitt)
- page 312, line 16: add "is" before"good"
(R. de Wolf)
- page 315, line 3: if k is odd,
the binomial Binomial(n-1,(k-1)/2), should be: Binomial(n-1,(k+1)/2) (S.Bova)
- page 316, line -12: missing parenthesisbefore">"
(R. de Wolf)
- page 317, Exercise 26.2: the lower bound
should be |E|m/(2m-1), just a bit more than 1/2 (R. de Wolf)
- page 326: Do not mix "two numbers"
in Schur's theorem with "two distinct numbers"; the situation x=y
is allowed (Chien-Chung
Huang)
- page 328, line
5: replace "j<n" by"j\leqn" (A. Utturwar)
- page 328, line
-3: "edges five" should be "edges and five"
- page 336, line
-7: "grater" should be "greater" (T. Mielikäinen)
- page 338, last
sentence before Thm.29.2: The correspondence is not 1-1 because not every
subspace forms a subcube (A. Razen)
-
page 338, last line: should be:
"... just like cliques are in graphs." (A. Razen)
-
page 339, proof of Thm. 29.3:
so as f(x) is defined the all-0 vector has no image. Correction: take N:=n(t-1)+1
and add 1 in the definition of f(x) (A. Razen)
- page 348
, lines -4: replace
\sqrt(\logn) by 2^{\sqrt(\logn)}
(H. Klauck)
- page 348
, line -1: replace \logn
by \sqrt{\logn}
(H. Klauck)
- page 349, line
-14: "coloring the N-cube" should be "coloring of the N-cube"
(A. Razen)
- page 342, lines
7, -6 and -3: replace \tau_m by \tau_n (A. Razen)
- page 345, line
3 before Theorem29.8:"then is" should be "is then"
- page 365 (references):
"Pefold" should be "Penfold" (D. Gunderson)
- page 368: index
entry "Hofmeister, T.,288" should be added
- page 369: index
entry for "Razborov,A." should be extended by pages 118-119
Return to
the home page of the book