List of Errata

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 C₀ and C₁ 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 "n^a "(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): V_k should be  V_r
• page 30, Ex. 2.8: "i_k" should be "i_s"   (Tim van Erven)
• page 32, line -8: A_l should be  A_k   (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 B₀ to A₀" (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:  A_i^a should be  A_i,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 v₁,...,v_kin A such that the vector u ₀=v₁+...+v_k 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    I₁   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 ₂    (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): "x_j" should be "y_j"
• page 217 ,line -10 (Hint):  "M_b r_b"  should be  "M r_b"  (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:   A_m  should be  A_n       (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 = 3k4^kln n" can be replaced by "l = 2k4^k   ln n"  (A. Utturwar)
• page 238, line-4:  x_i should be replaced by  x₁   (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):   " -2^k "  should be"  1/2^k "   (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  H_ab  by  H_aa   (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