## List of Errata (for the 2nd edition)

Since in this edition more than 1/3 of the stuff was replaced by a new one, and the rest of the text was also changed, new mistakes were unavoidable (unfortunately).
If you detect a misprint not in this list, please just drop me 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 (not just obvious typos/omisions, etc.) are marked red.
For the list of spelling errors and obvious (but still annoying) typos see here
• page 5, Eq. (1.5): should be $1-t>e^{-t-t^2}$ for $0 < t <0.6$ (Valdas Diciunas)
• page 6, line 1: Last equality should be $\leq$ (Esfandiar Haghverdi)
• page 23, line -3: Replace "$n$" by "$N$" (Siyuan Lu, Peter Stahlecker)
• page 30, line -1: Replace $f(z)$ by $f(x)$ (Jernej Azarija)
• page 35: Inequality (2.7) should be in the converse direction (Ronald de Wolf)
• page 38, Ex. 2.12, line -2: In $s \geq 2k$, the $k$ should be capitalized (Jernej Azarija)
• page 54, Dilworth lemma: The proof via maximal chains does not go (Esfandiar Haghverdi)
Correct argumentation was in the 1st edition; it is here
• page 62, line -5: Replace "trail ending at $y$ by $1$" to "trail ending at $x$ by at least $1$" (Jernej Azarija)
• page 67, line -15: Replace "subsets of vertices" by "subsets of vertices is" (i.e. add "is") (Jernej Azarija)
• page 83, line 5: Here $E$ is the set of edges of $G$ (Jernej Azarija)
• page 86, line 2 of Ex 5.10: Sets $A$ and $B$ are assumed to be disjoint; this is now only implicit from the fact that $G$ is bipartite (Ronald de Wolf)
• page 97, Ex. 6.7: The graph ${\cal G}_s$ should be formed by joining $A$ and $B$ iff all vertices $u\in A\setminus B$ and $v\in B\setminus A$ are adjacent in $G$ (Vikram Kamat)
• page 106, Ex. 7.2: $|{\cal F}|$ should be $|{\cal F}'|$ (David Kotschessa)
• page 106, Ex. 7.6: Replace "Let $=\{B_1$" by "Let $\{B_1$", i.e. remove the equality sign (David Kotschessa)
• page 108, proof of Thm. 8.2: Line -8 redundand ")". Also, the use of $r$ as the length of a longest antichain for both $P$ and $P'$ is a bit confusing (Ronald de Wolf)
Here is a more detailed proof, as well as a yet another proof.
• page 109, line -4 before Thm. 8.3: Replace $k=n$ by $k=n+1$ (Esfandiar Haghverdi)
• page 109, line -1 before Thm. 8.3: Start with the empty set. Also, here we mean permutations without fixed points, i.e. derrangements (Esfandiar Haghverdi)
• page 111, 1-2 lines before Sect. 8.3: In this (simplified) argument, the length $L$ is twice larger than stated: $m^2$ many blocks $\overline{D_i} C_j$ both of length at most $k$ yields $2km^2$. To get rid of this factor of 2, Lipski (1978) used a bit more subtler argument (Markus Hartmair)
• Page 111, all throughout before 8.3: If $k$ is odd, one should replace $k/2$ by $\lfloor k/2\rfloor$ (Esfandiar Haghverdi)
• page 117, Ex. 8.1: ${\cal F}$ is over a universe of size $n$ (Ronald de Wolf)
• page 117, Ex. 8.3, Hint: The $Y_i$s must be $(a-s)$-element, not $s$-element subsets (Brent McKain)
• page 125, 2 lines before Eq. (9.3): replace $D_0$ and $D_1$ by $C_0$ and $C_1$ (Ronald de Wolf)
• page 133, Ex. 9.10: Replace "has depth" by "has depth at least" (Ronald de Wolf)
• page 137, line -3: replace $t_n(A)$ by $t_{n-1}(A)$ (Peter Stahlecker)
• page 148, line 1: replace $a_k$ by $a_k+1$ (Peter Stahlecker)
• page 157, Thm. 11.3: Replace the lower bound by $m^{1/2}/4$ (the lower bound at the end of the proof was in terms of $n=m/2$) (Mahdi SafarNejad-Boroujeni)
• page 162, last line: should be $k+m/k\leq l+2$, not $\geq$ (Mahdi SafarNejad-Boroujeni)
• page 169: In Thm 12.7 (and in its proof), $Z_v$ stands, of course, for the field of order $v$ (not just for an additive Abelian group - we could not multiply there) (Jamie Radcliffe)
• page 176, Ex. 12.8: Additional condition on $S$ is missing: with no three points of $S$ on a line (Mahdi SafarNejad-Boroujeni)
• page 176, Ex. 12.9, hint: replace "even" by "odd" and vice versa (Mahdi SafarNejad-Boroujeni)
• page 176, Ex. 12.10: replace $A\neq B$ by $A\not\subseteq B$ (Mahdi SafarNejad-Boroujeni)
• page 183, line -10: Replace "In particular, (13.5) yields" by "In particular, if $A$ is an adjacency matrix of a regular graph, then (13.5) yields" (Esfandiar Haghverdi)
• page 184, line 6: Missing coefficients $a_i$, so replace $\langle u^i,\lambda_j u^j\rangle$ by $\langle a_iu^i,\lambda_j a_ju^j\rangle$ (Peter Stahlecker, Esfandiar Haghverdi)
• page 189, line 4: replace "largest $i$" by "smallest $i$" (Hiroaki Yamanouchi)
• page 196, line 4:replace $\mu_1,\ldots,\mu_t$ by $\mu_{I_1},\ldots,\mu_{I_t}$ (Ronald de Wolf)
• page 197, line -2: Here $X$ is the underlying $n$-element set (Jernej Azarija)
• page 204, line 1: replace $g_i(c_j)=0$ by $f_i(c_j)=0$ (Hiroaki Yamanouchi)
• page 204: remove the 4-th paragraph with repeated definition of $rk_R(A)$ (Peter Stahlecker)
• page 207, line 12: dimensions should be $a_i\times b_i$ (Jernej Azarija)
• page 209, line -6: replace $(R)$ by $(M_R)$ (Peter Stahlecker)
• page 210, Ex. 14.5: Should be "at least when $k\times k$ and $(n/k)\times (n/k)$ Hadamard matrices exist" (Mahdi SafarNejad-Boroujen)
• page 215, in the proof of Lemma 15.2: Lemma 13.5 --> Theorem 13.5 (Esfandiar Haghverdi)
• Page 216: at the end of the proof: replace $\lambda stn - stdn$ by $stdn - \lambda stn$ (Esfandiar Haghverdi)
• page 216, line -4: replace $dy_i$ by $d^ty_i$ (Peter Stahlecker, Esfandiar Haghverdi)
• page 214 ff: The eigenvalues should be orderd by their decreasing absolute values $|\lambda_1|\geq |\lambda_2|\geq \ldots\geq |\lambda_n|$. Thus, through, $\lambda$ should stand for $|\lambda_2|$. In particular, the spectral gap $\lambda_1-\lambda$ of $K_n$ is $n-1-|-1|=n-2$, not $n-1-(-1)=n$ (Maria Axenovich, Brent McKain, Ronald de Wolf)
• page 217, Thm. 15.4: "incidence matrix" should be "adjacency matrix" (Maria Axenovich)
• page 217, line 12: The right-hand side of the displayed formula must have a factor $|S|$ added to it (Ronald de Wolf)
• page 218, line 11: replace $(x,y+y)$ by $(x,x+y)$ (Ronald de Wolf)
• page 220, before Claim 15.7: replace ${\cal A}(x,v)$ by ${\cal A}(x,u)$ (Peter Stahlecker)
• page 220, line -5: here $n$ is the number $|V|=2^m$ of vertices, not the length of the input $x$ (Ronald de Wolf)
• page 224, line 3: Replace $\tbinom{n+d}{n}$ by $\tbinom{n+d}{d}$; this is the same but why switch notation? (Ronald de Wolf)
• page 229, Thm. 16.8: "... there are exists a point ..." (Peter Stahlecker)
• page 231, Thm.13: remove word "spanning" (Maria Axenovich)
• page 235, Ex. 16.5: replace $|S_i|\geq t_i$ by $|S_i| > t_i$ (Maria Axenovich)
• page 239, line 16: replace "of degree at most $\ell"$ by "of degree at mot $t$" (Peter Stahlecker)
• page 250, line -3, 3rd term: missing $s$, i.e., replace $e^3d^4$ by $e^3d^4s$ (Peter Stahlecker)
• page 263, line -2: replace $\mathrm{dist}(x,y)$ by $\mathrm{dist}(u,v)$ (Peter Stahlecker)
• page 278, Ex. 18.14: Notational inconsistency. Replace $\log n$ by $\ln n$, and $\mathrm{proj}_S(\mathbf{A})$ by $\mathbf{A}\upharpoonright_S$; the latter notation for the projection was used earlier in Sect. 3.3 (Ronald de Wolf)
• page 283, proof of Thm. 19.4: Strongly speaking, the event $A_v$ must be conditioned on the event $E$ that each of $r$ colors are used (Jose Falkner).
Fortunately, the conditioning will not effect much the given upper bound on $\mathrm{Pr}[A_v]$, because $\mathrm{Pr}[\neg E]\leq r(1-1/r)^n \leq r\mathrm{e}^{-n/r}$ is small enough.
• page 284, line 4: replace "Since this set ..." by "Since the set $\{A_u\colon N(u)\cap N(v)\neq\emptyset\}$ ..." (Peter Stahlecker)
• page 286, Thm. 19.7: $r$ should be the ceiling of $k/\log k$, not the floor (Brent McKain)
• page 293, line -5: replace "and (1.4) in Chap. 1.5" by "and (1.5) in Sect. 1.1" (Peter Stahlecker)
• page 319, line 5: replace $\mathrm{Pr}[A=i]$ by $\mathrm{Pr}[A=a_i]$ (Peter Stahlecker)
• page 351, line 4: missing "$t$". So, replace $x\colon x\cdot \in S$ by $x\colon x\cdot t\in S$ (Peter Stahlecker)
• page 362, line 13: replace $C(b,i_1,i_1)$ by $C(b,i_1,i_2)$ (Peter Stahlecker)
• page 367, line 2: replace "Lemma 15.2" by "Lemma 15.5" (Peter Stahlecker)
• page 373, Proof of Thm. 26.3: To fit within $[N]$ one should take $f(x)=x_1+\cdots+x_n-n+1$ , that is, with $-n+1$ (Josse van Dobben de Bruyn)
• page 381, lines -16 and -14: vectors have length $k$, not $n$. So, replace $x_n$ by $x_k$ (Peter Stahlecker)