Invitation to Discrete Mathematics (Jiri Matousek and Jaroslav Nesetril)
Errata
For the second edition (2008)
- p. 27, the King's Dream formula, x and y should be interchanged
in the formula for the x-coordinate of f(x,y). (Noted by Hugo Ishimaru.)
- p.41, Exercise 2,
instead of composition of R and R^{-1} there should be intersection.
(Noted by Jakub Tomek.)
- p.44, the definition of the lexicographic ordering for pairs
should compare a_1 to b_1 and a_2 to b_2, as in the general
definition below. (Noted by Wai Yan Pong.)
- p. 49, second proof of Theorem 2.2.3, |L_x| = {x} it should
say L_x = {x}. (Noted by Mario A. Lopez.)
- p. 49, Thm. 2.2.3, X should be assumed nonempty.
(Noted by Sang-il Oum.)
- p. 51, Exercise 3(b), |x| should be |X|. (Noted by Mario Lopez.)
- p. 58, Exercise 3, "17" should be "16".
(Noted by Sang-il Oum.)
- p. 58, Exercise 6(b), "(c)" should be "(a)".
(Noted by Sang-il Oum.)
- Exercise 3.2.6, part (b) is wrongly formulated (and false as stated).
The relation should be {(i,j): i<j and pi(i)>pi(j)}.
(Noted by Ivan Vukovic.)
- p. 118, Exercise 5(d), an assumption is missing; namely, the graph
should be connected. (Noted by Lukas Klouda.)
- p. 119 middle, "path from v0 to vn of length t" should be "path from v0 to vt of length t". (Noted by Sang-il Oum.)
- p. 233, Exercise 6, part (b) fails for n odd in the stated
setting; to fix this, one should make one of the two inequalities
in the definition of p(a_1,...,a_n) non-strict.
(Noted by Boris Bukh.)
- p. 241 bottom, the first sum in the three-line display should also
go up to n-1, not n. (Noted by Sang-il Oum.)
- p.323, the remark following Corollary 11.3.2 is wrong
and should be omitted (since r(2)=2=2^{2/2}). (Noted
by Eva Kopecka.)
- p. 420, hint 6.3.8(c), e>=3f-n should be 2e>=3f-n.
(Noted by Sang-il Oum.)
- Hint 3.1.5, q^n-q^i should be q^n-q^{i-1}.
(Noted by Russ Woodroofe.)
- Hint 12.3.10, the expression to be considered is (6+sqrt 37)^n +
(6-sqrt 37)^n (plus instead of minus). (Noted by Boris Bukh.)
For both 1st and 2nd printing of the first edition
There is a mistake, also in the forthcoming new edition, for which
I can't check the page numbers at the moment:
In Ex. 5 of the last section of "Double-counting",
f(m/2n) should be f(2m/n). (Noted by Nabiha Asghar.)
Another newly found mistake is in Exercise 9.4.9 (1st edition),
where one should assume that the point o lies below all
of the lines (otherwise, the solution doesn't
work quite as indicated in the hint).
(Noted by Raabia Mumtaz.)
- p. 5 middle, there are 5 ways to partition the coins: 2+2 was omitted!
(Noted by Omar, UIUC)
- p. 69-70, the given definition of the relation f=O(g) is not suitable
for situations where g(n)=0 for some values of n. (For example,
n=O(n ln n) would not hold according to this definition.)
Hence it is better to take the second definition mentioned later,
with n_0. (Noted by Konrad Swanepoel.)
- P. 73 Exercise 1, the relation is not a partial ordering because
it is not antisymmetric. The right statement should be that
the relation is transitive. (Noted by Konrad Swanepoel.)
- p. 96, exercise 2.8.11 (b), the subscript of p is missing in the
numerator (should be p_i instead). (Noted by Nabil Mustafa.)
- p. 110, Corollary 3.2.5, k>=1 should be k>=0.
(Noted by Bernd Bischl)
- p. 111, Exercise 7, the function d should go into natural numbers
plus 0. (Noted by Bernd Bischl)
- p. 111, Exercise 10, "incidence matrix" should be
"adjacency matrix". Same for Exercise 11 on page 112.
(Noted by Hans Mielke, Berlin)
- p. 119 first displayed formula, missing e_m between v_{m-1} and v_0
- p. 130, Fig. 3.5 left, the labels of the middle arrows should
be swapped (noted by Pavel Vavra, Prague)
-
p. 132 middle "Instead of ..." the first "vertex" should be deleted.
(Noted by Hans Mielke, Berlin)
- p. 145, definition of planted tree in the middle:
should be "...plus some fixed drawing of T..."
(Noted by Hans Mielke, Berlin)
- p. 151, line -7, one should refer to Exercise 4.1.2 instead
of Theorem 4.1.2(v) (Noted by Bernd Bischl)
- p. 159 2nd line, e\in \check E should be e\in\check E \setminus E'
- p. 160, Exercise 6, line 4: insert "of" after "tree".
(Noted by Hans Mielke, Berlin)
- p. 179 middle, "Such graphs have an essentially unique
planar drawing": the explanation "up to a continuous deformation
of the plane and mirror reflection" is incorrect since we can
also choose which face is the outer one. Such explanation applies
to drawings on a sphere.
(Noted by Hans Mielke, Berlin)
- p. 188, 4 lines above Prop. 5.3.4, correctly "since a triangle-free
graph on 6 vertices has at most 8 edges" (K_{3,3} has 6 vertices, not 9).
(Noted by Delphine Hachez)
- p. 201 Exercise 12, the inequality |L(v)|<=k should be
the other way round: |L(v)|>=k.
(Noted by Hans Mielke, Berlin)
-
p. 214 2nd paragraph from below, "The only way two sequences with
the same partial pairing may differ is that one has more unmatched
right parentheses on the left than the other":
it may also happen that there are more unmatched left parentheses
on the right.
(Noted by Hans Mielke, Berlin)
- p. 215, line 10, the inequality sign between f(x) and f(y) should
be the "curved" one (the relation on Y) (Noted by Bernd Bischl)
-
p. 231, the proof for the Prufer coding is incomplete. It should still
be proved that the reconstruction algorithm always produces a tree, for
any input sequence. A reasonable way of doing this is by the tree-growing
lemma. The details should appear here in the future.
(Noted by Martin Klazar, Prague)
- p. 246, at the end of the proof of Prop. 8.1.5(ii),
the line ax coincides with L_i (rather than with L).
[2nd edition too]
(Noted by Nabil Mustafa.)
- p. 250, Exrecise 10b, "or A_1=A_2" should be added to the definition
of the relation, so that reflexivity holds. (Noted by Bernd Bischl)
- p. 250 bottom, it is mistakenly asserted that the mentioned theorem
does not exclude the existence of a projective plane of order 6;
in fact it does (6 gives remainder 2 mod 4 and it cannot be written
as a sum of two squares).
- p. 252 the first picture should be different (without the lines
and with point labels)
(Noted by Hans Mielke, Berlin)
- p. 274 l. 4 "We prove the SECOND of these claims"
(Noted by Hans Mielke, Berlin)
- Page 331, last displayed formula, m(2m-1)/3-m on the left-hand side
should be m(2m-1)/3+m (noted by Hans-Joachim Brenner).
- p. 333 footnote "block" (instead of "blocks")
- p. 334, Def 11.1.1 (2),
delete the first "of"
- p. 338, ex 11.1.2, "as" -> "an"
- p. 338, ex. 11.1.4, for i=3, i+1 means 1
(Noted by Hans Mielke, Berlin)
- P. 345, ex. 11.3.4, the statement is false and the solution
in the hint is wrong (of course). (Noted by Yuji Odaka)
- P. 361, Exercise 1, {0,1,...,m} should better be {0,1,...,m-1}
in order to match the probability 1/m. (Noted by Konrad Swanepoel.)
- P. 365, missing factor a_{ij}
the formula in item 5 (expansion according to a row);
the expression following the sum sign should be (-1)^{i+j} a_{ij} A_{ij}.
-
p.366, l. 10 from below: "regular matrices" should be "nonsingular matrices"
-
p. 368, 3rd paragraph, def. of linear dependence: "v_1,...,v_n in V" should
be "v_1,...,v_n in A" and "nonzero alpha_1,...,alpha_n\in K"
should be "alpha_1,...,alpha_n\in K, not all zero" (noted by Emo Welzl,
ETH Zurich)
- Hint to Exercise 2.3.2(b): one should divide into n-r+1 groups,
instead or n-r groups. (Noted by M. Suda, Prague)
- Hint to Exercise 2.3.7: the equation should be
k_0+k_1+...+k_n=n-1. (Noted by J. Zouhar, Prague.)
- Hint to Exercise 2.8.7(c): A_n should be A_m. (Noted by Jana Chlebikova,
Bratislava)
- Hint 2.8.9 is wrong (but maybe there are too
many hints anyway...).
(Noted by Hans Mielke, Berlin)
- Hint 3.3.12: instead of "kn must be odd" should be
"kn should be even".
(Noted by Hans Mielke, Berlin)
- Hint to Exercise 10.2.5: (1-x)^3 in the last expression
should be (1-x^3)^3. (Error noted by J. L. Doncel, Coruna,
error in erratum noted by Petr Kovar, Ostrava.)
-
Hint to Exercise 10.3.8: should be (n+1)/2^n (noted by Hans-Joachim Brenner).
-
Hint to Exercise 10.7.6(d): in the first bound (for ln r_n), P_n(x^j) should
be replaced by (P_n(x^j)-1). Consequently, the term of the final sum should
be (1/j)[exp(Cx^j/(1-x^j))-1], and then the sum really converges as claimed.
(Noted by Andreas Weiermann, Muenster.)
- Hint 11.2.6(a), "them" -> "then".
These are corrected in the 2nd printing:
-
page 43, 2nd line from the bottom: "x is drawn higher than y" should be
"y is drawn higher than x". (Noted by Mel Hausner, NYU.)
-
page 116, line 9: should be (0,0,0,0,0) rather than (0,0,0,0). Next line:
"of the graph with 5 vertices..." (rather than 4). (Noted by Mel Hausner,
NYU.)
-
page 172: the first picture should be different (a drawing of K_5 on a
torus).
-
Theorem 5.2.1, 5th line of the statement, R^2\ gamma should be R^2\k (Noted
by Emo Welzl, ETHZ.)
-
page 290, QUICKSORT example: the triple (3,2,1) should be (3,1,2), with
subsequent changes down the line. (Noted by Mel Hausner, NYU.)
-
page 380, hint 2.3.7: k_0 should be f(1)-1. (Noted by Mel Hausner, NYU.)