"Extremal Combinatorics" -- List of errata

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 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 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 "n^a "(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): V_k should be V_r
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: 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 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 B₀to A₀" (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: A_i^a should be A_i,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 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 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 I₁ 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 ₂ (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 224, Markov's inequality: lambda should be positive (G�bor Nyul)
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 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): " -2^k" should be" 1/2^k " (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 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 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