Extremal Combinatorics

List of Errata (for the 2nd edition)

If you detect a misprint not in this list, please use the online form  or just drop me an email (in the former case, it would be good to know your name, just to name the corrector). Contributor’s names appear  in parenthesis. I am grateful to all you, also in the name of other readers! "Line -x" means x lines up from the bottom. Misleading errors in mathematics (not just obvious typos/omisions, etc.) are marked red.

• page 5, Eq. (1.5): should be $1-t>e^{-t-t^2}$ for $0 < t <0.6$ (Valdas Dičiünas)
• page 6, line 1: Last equality should be $\leq$ (Esfandiar Haghverdi)
• page 6, Eqs. (1.8) and (1.9): replace "$-k^3/6n^2$" by "$+k^3/3n^2$" (Simon Apers)
• page 20, line -3: Replace "modulo $2$" by "modulo $2n$" (Vesna Iršič)
• 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 49, line 2 after Eq. (3.4): replace "$c_v\in S_0\cap S(v)$ and $c_u\in S_1\cap S(u)$" by "$c_u\in S_0\cap S(u)$ and $c_v\in S_1\cap S(v)$" (Yuxiang Lin)
• 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 130, Theorem 9.14: The argument used in Case 2 of the proof is buggy (Ho Boon Suan)
  Here is my corected argument.
• 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 217, Lemma 15.5 [the same "absolute value" mistake as on page 214]: replace $\lambda=\lambda_2$ by $\lambda=\max\{|\lambda_2|,\ldots,|\lambda_n|\}$ [because for absolute values, it may be that $|\lambda_2|\leq \ldots\leq |\lambda_n|$] (Ying Miao)
• 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 294, Thm. 20.2: assumption $k\geq 1$ is missing (Lutz Warnke)
• page 305, lines 11-12: parameter $s$ in $\mathrm{Pr}[Y=s]$ runs over all numbers of the form $a-r$, where $a$ is an integer in $[-t+r,t+r]$, and $r=\mathrm{E}[X]$ is a fixed real number (there are at most $2t+1$ such integers $a$) (Dan Hefetz)
• page 311, line -1: $a^2/(a+b)$ should be replaced with $a^2/(a+2b)$ (Vesna Iršič)
• 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)