The 2nd, substantially expanded and revised edition is in press. All errors listed below are corrected in it.

Extremal Combinatorics

List of Errata (for the 1st edition)

Last modified: November 23,  2008



If you detect a misprint not in this list, please use the online form  or just drop an email.


Contributor’s names appear  in parenthesis. I am grateful to all you!

"Line -x" means x lines up from the bottom. Misleading errors in mathematics are marked boldface.
[Some typos in names are listed at the end.]

  • 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 have the same 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 24, line -4: "2kw^k" should be "2k^2w^k"   (Dmitry Gavinsky)
  • 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.2: Assume that n is even    (Dmitry GavinskY)
  • page 29, Ex.2.3:  The condition  "A\neq B" should be removed (Qiqi Yan)
  • page 29, line -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 30, Ex. 2.10: "every every" --> "every"    (Dmitry Gavinsky)
  • 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 proof of 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 "consecutive" (Tim van Erven) and the first set of pigeons should be (2i,2i-1) instead of (i,i+1) (Wouter Koolen-Wijkstra)
  • page 53, Ex. 411: "constant sequence" --> "constant subsequence"  (R. de Wolf)
  • 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 63, Ex. 5.4: "we can a new row add" --> "we can add a new”  (R. de Wolf)
  • page 64, Ex. 5.5:  It must be assumed that the sequence has a system of distinct representatives (D. Zuckerman); also, “=f(r,m)” should be “\geq f(r,m)” (we can have strict inequality if r>m)    (R. de Wolf)
  • 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 part of G1seen by Alice with the part of 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 (after the proof of Claim7.6): all three occurrences of  "F"  should be replaced 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 Journal of Math. 122 (2001), 243-251.
  • page 97, line 4: "irreflexive" should be replaced by "antisymmetric" , (Narayanan N.)
  • page 102, line 6: one its --> one of its  (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 105, Thm. 9.13: "k+2" should be "k+1"   (P. Zumstein) [ his comment]
  • 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 109, Proposition 10.2:  Thijs van Ommen, a student of  R. de Wolf, shows that the solution to Proposition 10.2 is optimal.  Prop-10-2.html
  • 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 occurrences 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". Note that the 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 is trivial).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 "{\cal F}_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 x,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 154, 3rd line of the proof: the set should be {(x,B):B\in D, a,x\in B, x\neq a}, because "a" is fixed here before (Gábor Nyul)
  • page 155, line -1:  "Chap.14"  should be "Chap. 15"  (S. Hada) and theorem should be Thereom 15.8 (Gábor Nyul)
  • 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 162, line -8: one L should be calligraphic (Gábor Nyul)
  • 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 affine space  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 174, Lemma 14.8: k must be strongly larger than n/2   (Pawel Wojda)
  • page 176, line 4 of Sec 14.3:  remove "a" before "members"   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 zero" 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" should be "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,...,vk in 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 188, Ex. 14.16, Item (i): Replace “\leq |H_i|” by “<|H_i|”  (R. de Wolf)
  • 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 functions vanish."   (S. Akbari)
  • page 190, Exercise 14.26 (Hint): should be "for every  v  in  span A"  (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 vectors in  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 224, Markov's inequality: lambda should be positive (Gábor Nyul)
  • 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 244, Ex. 19.1 (hint): Use “1+t<e^t”; the form 1-t<e^{-t} is also OK, but is somewhat confusing hint since we actually want to obtain that (1+1/d)^d\leq e.    (R. de Wolf)
  • 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(\log n) by  2^{\sqrt(\log n)} -->   resp. corrections on page 348 (H. Klauck)
  • page 261, Ex. 20.6: “given a graph” -->  “given an n-vertex graph”   (R. de Wolf)
  • 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 285, Ex. 23.4: the inequality goes the wrong way (R. de Wolf)
  • page 285:  Exercise 23.8 is wrongly stated. Here is a correction by R. de Wolf  Ex-23-8.html
  • 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 coefficient Binomial(n-1,(k-1)/2), should be: Binomial(n-1,(k+1)/2) (S. Bova)
  • page 316, line -12: missing parenthesis before">"  (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\leq n" (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(\log n) by 2^{\sqrt(\log n)} (H. Klauck)
  • page 348 , line -1: replace \log n by \sqrt{\log n}  (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


There are also some annoying typos in Hungarian (and other) names and words observed by Gábor Nyul:
  • page 81, line 7 and 8: "R\H{o}dl" should be "R\"{o}dl" two times
  • page 113, line -4: "Bolob\'{a}s" should be "Bollob\'{a}s"
  • page 261, exercise 20.5: "Red\'{e}i" should be "R\'{e}dei"
  • page 336, exercise 28.5: "Knesers's" should be "Kneser's"
  • page 351, line -4: "Erd\"{o}s" should be "Erd\H{o}s"
  • page 352, line -3: "Polya" should be "P\'{o}lya"
  • page 353, reference Ahlswede et al: "Szekely" should be "Sz\'{e}kely"
  • page 360, line 1: "Polya" should be "P\'{o}lya"
  • page 361, in reference of Kövári et al: "T\'{u}ran" should be "Tur\'{a}n"
  • page 364, in reference of Redei: "Red\'{e}i" should be "R\'{e}dei"
  • page 365, in reference of Szele: "Matematicko Fizicki Lapok" should be "Matematikai Fizikai Lapok"
  • page 369, name of Redei: "Red\'{e}i" should be "R\'{e}dei", and "Szekely" should be "Sz\'{e}kely"

Return to  the home page of the book