Lectures on Discrete Geometry (Jiri Matousek)

Errata and remarks

• P. 6, the second remark under the separation theorem, stating that the convex hull of a closed set X equals the intersection of all closed halfspaces containing X, is false, since the convex hull of a closed set need not be closed. (Noted by Uli Wagner.)
• P. 7, the proof of the separation theorem (the case of general C and D, non-strict separation) doesn't work as stated. (Noted by Wolfgang Weil.) First of all, C is not contained in the union of the C_n but only in their closure. Second, and more serious, the C_n and D_n as defined in the proof need not be disjoint! (For example, take C as a union of an open halfplane H and a point p on its boundary, and D as another point q on the boundary of H, and use p and q as centers of the shrinking.) To have them disjoint, one needs to choose the center of the shrinking as a point in the relative interior. This requires more work, and with this adjustment, this proof is perhaps no longer the method of choice. Here is an outline of one possible proof. First, a standard step for simplyfing matters is noticing that separation of C from D is equivalent to separating A:=C-D={x-y: x\in C, y\in D} from {0}. Let B be the closure of A. If 0 is not in B, we are done. Otherwise, a small argument shows that 0 must be on the boundary of A, and so we can choose a sequence {x_n} of points outside B converging to 0 and verify that separating hyperplanes of B and x_n have a convergent subsequence whose limit is a separating hyperplane (containing 0 and with all of A on one side).
• P. 8 bottom, the Bonnice-Klee theorem should read "Any k-interior point of conv(X) is a k-interior point of conv(Y) for some Y\subseteq X with at most max(2k,d+1) points, where x is called a k-interior point of a set C if x lies in the relative interior of the convex hull of some k+1 affinely independent points of Y." (Noted by Sergio Cabello.)
• P. 9, Exercise 4(b), it is to be proved f(conv(X))=conv(f(X)). (Noted by Sergio Cabello.)
• P. 9, Exercise 6(b), we need to assume that C is a closed convex cone. (Noted by Yonathan Mizrahi.)
• P. 19, in Proposition 2.1.3 we want N and n to be at least 1, but for m we have to admit m=0 as well. Similarly in Exercise 2.2.5. (Noted by Marek Scholle.)
• P. 21, 2nd line from below: BU should be ZU. (Noted by Sergio Cabello.)
• P. 22, l. 16, Example 2.1.3 should be Proposition 2.1.3. (Noted by Sergio Cabello.)
• Exercise 2.1.2, we should really have k+1 points instead of k (with k the result is valid too but the natural statement is with k+1). (Noted by Leonard Schulman.)
• P. 23, the conclusion of the proof of Theorem 2.2.2 is oversimplified; the point v' need not lie in P. One needs to rewrite v'=\sum_{j=1}^{i-1}(\alpha_j+1)\gamma_j z_j + \gamma_i\alpha_i w, and reduce once more; that is, to consider v'' = \sum_{j=1}^{i-1} fract.part((\alpha_j+1)\gamma_j)z_j +\gamma_i\alpha_i w, obtaining \gamma_i=0 as before. (Noted by Sergio Cabello.)
• P. 23 (what an unfortunate page!), Bibliography and Remarks, 3rd line: An assumption is omitted, namely, that C has to be a star body, i.e. a compact set containing 0 in the interior and such that x\in C implies tx\in C for all t\in[0,1]. A few lines below: "det(Lambda) > D" should be "det(Lambda) < D". (Noted by Sergio Cabello.)
• P. 34, the 6-hole problem was resolved in 2005 by Tobias Gerken, who showed by a clever case analysis that any set containing 9 points in convex positions has a 6-hole, and independently by Carlos M. Nicolas. Gerken's proof was simplified by Pavel Valtr to about 4 pages (but one needs more than 9 points in convex position to start with, and hence the resulting upper bound for n(6) is worse).
• P. 44, above the picture, the Fano plane is of order 2, not 3 (noted by Gabriel Nivasch).
• P. 46, "Point-plane indicences", the first upper bound for point-plane incidences is attributed to Aronov and Agarwal by mistake. The result can be found in a paper by Guibas, Overmars, and Robert [Comp. Geom. Theor. Appl. 6(1996) 215-230]. (Noted by Yoshio Okamoto.)
• P. 49, l. 6, "at most 8 distinct curves \gamma_{ij}" better "at most 8 of the curves \gamma_{ij}" (some of the curves may conicide)
• P. 52, l.2, the constant should not be 1/4 (but rather 4^{-1/3}). (Noted by Akyoshi Shiboura.)
• P. 53, l. 10 from below: 2^{r-1}/16 should be n2^{r-1}/8. (Noted by Micha Sharir and his students.)
• P. 54, Exercise 4.2.1, the inequalities should be reversed (n^2 >= m and m^2 >= n). (Noted by Abbas Mehrabian.)
• P. 55, in the proof of the crossing number lemma we should assume that no two edgs sharing a vertex cross in the chosen drawing of G, for otherwise, E[x']=p^4 x need not hold. For straight-line drawings this assumption is satisfied automatically, and for curvilinear drawings it is easily enforces.
• P. 56, 2nd line below the picture, P should be E. (Noted by Nati Linial.)
• P. 57, line 6: "closed under REMOVING edges" (instead of addding). (Noted by Uli Wagner.)
• P. 70 Exercise 4.5.2, O(n\sqrt m + m) (instead of O(n\sqrt m + n)). (Noted by Sergio Cabello.)
• P. 72, footnote, the number of pairs of possible unbounded rays is of order n^4, rather than n^2 (which doesn't matter for the proof). (Noted by Gabriel Nivasch.)
• P. 74, above the picture, t/q+2 should be t/q+3. (Noted by Salman Parsa.)
• P. 77, picture, the top vertex of the front square should be 1423 (rather than 1342). (Noted by Petr Skovron.)
• P. 81 exercise 6(b), C^* equals the CLOSURE of the stated convex hull. (Noted by Uli Wagner.)
• P. 84, line 2, < \sigma,\leq > 1 should be < \sigma, x >\leq 1.
• P. 89, the elements 15 and 235 shouldn't be connected in the face lattice, while 35 should be connected to 235. (Noted by Yoshio Okamoto and by Tomasz Gdala.)
• P. 97 picture, the labels gamma_5 and gamma_6 should be gamma_4 and gamma_5. (Noted by Petr Skovron.)
• P. 98, last line of the proof of Theorem 5.4.5, the binomial coefficient should be n-k-1 choose k-1. (Noted by Micha Sharir and his students.)
• P. 101, in the sentence at lines 6-8, the words "upwards" and "downwards" should be interchanged. (Noted by Yoshio Okamoto.)
• P. 102, last line of the first paragraph, "simple" should be "simplicial". (Noted by Micha Sharir and his students.)
• P. 108 middle, the matrix A should be (d+1)x n, instead of d x n. (Noted by Yoshio Okamoto.)
• P. 123, last line of exercise 5.7.2, n^k should be n^{k+1}. (Noted by Uli Wagner.)
• P. 129 Exercise 6(b), d-tuples should be (d+1)-tuples (twice). (Noted by Yoshio Okamoto.)
• P. 131, as I've learned from Ricky Pollack, Oleinik and Petrovskii only proved bounds for the sum of Betti numbers (and in particular, for the number of connected components) of an algebraic set, i.e. the intersection of the zero sets of n polynomials, under the additional assumption that these zero sets are smooth hypersurfaces. Thom and Milnor obtained more general bounds but still for algebraic sets. Sign patterns were explicitely considered only later (but a reduction of this problem to the number of connected components of a suitable algebraic set is not very hard).
• P. 139, Exercise 2(c): There are actually quite simple examples (which I've overlooked, unfortunately) showing that the number of intersection graphs of convex sets is at least 2^{const. n^2}. Recently Pach and Toth ("How many drawings are there?", manuscript, 2002) determined the right constant in the exponent: the number is 2^{(3/8+o(1))n^2}, for both intersection graphs of planar convex sets and intersection graphs of planar curves.
• P. 144 in the displayed formula below Lemma 6.3.2, (k+1)^{-d} should be (k+1)^d. (Noted by Hiroshi Maehara.)
• In the last displayed formula in the proof of Lemma 6.3.2, (r/dn) should be (r/2n). (Noted by Yoshio Okamoto.)
• P. 158 top picture, there is a missing case (a trapezoid with a top side, bottom side, left vertical side but unbounded on the right. (Noted by Gabriel Nivasch.)
• P. 159, above the second displayed formula from below, t(r/n) should be t(n/r). (Noted by Uli Wagner.)
• P. 163, the remark on optimal cuttings for arrangements of spheres is unfounded (or confusing at best). As far as I could find, the best known decompositions for arrangements of spheres need O(n^d log n) cells, and the corresponding (1/r)-cuttings have r^d log r cells, probably slightly suboptimal. This error of mine, unfortunately, has been propagated in the (marvellous) paper of Jozsef Solymosi and Van Ha Vu, Near optimal bounds for the Erdos distinct distances problem in high dimensions [Combinatorica 28,1 (2008): 113-125].
• P. 174, displayed equation lambda_3(n) <= 2n alpha(n) + O(sqrt(n alpha(n))), the lower-order term should be O(n sqrt(alpha(n))). (Noted by Gabriel Nivasch.)
• P. 178 middle, definition of "nonrepetitive segment", the index of the last symbol a_{i+k} should be i+k-1 (noted by Pavel Valtr)
• P. 182 Exercise 1, \psi_s(n,m) should be \psi_s(m,n). (Noted by Yoshio Okamoto.) In part (d), it seems that the tools given in (a)-(c) do not lead to the claimed exponent of the logarithm in a simple way. One can get some suitable exponent c(s) for every s. (Noted by Gabriel Nivasch.)
• P. 203, colored Tverberg theorem: it should be said that the A_i are (d+1)-element sets. (Noted by Peter Landweber.)
• P. 204 4th line of the last paragraph, A should be X. (Noted by Gabriel Nivasch.)
• P. 205 line 2: T_3(X) is always nonempty for a (2d+3)-point set in dimension d. A correct formulation is "for a set X in R^d, where d is a part of input, is NP-complete." (Noted by Emo Welzl.)
• P. 210, it is incorrectly claimed that EVERY centerpoint of X is contained in 2/9 of all X-triangles. Boros and Furedi showed this only for a point of the maximum depth (which may be larger than n/3 for some X). (Noted by Nabil Mustafa.)
• P. 214 above the picture, "3-regular" should be "3-uniform". (Noted by Yoshio Okamoto.)
• P. 218 Lemma 9.3.2: the sets C_i should also be compact, for otherwise, the implication (i) implies (ii) need not hold. (Noted by Uli Wagner.)
• P. 219, line 9: "no more than 2^{d-1} halvings" should be "no more than 2^d halvings". (Noted by Gabriel Nivasch.)
• P. 224, picture, the second Y_3 should be Y_4. (Noted by Salman Parsa.)
• P. 225 line -8 (after "Therefore,"), the second inequality is not valid, and so one needs to carry the middle term over to the subsequent calculation, which thus becomes more complicated. Here is a fix. (Noted and correction suggested by Jan Kyncl.)
• P. 236 footnote, the known result is weaker than claimed there: The assumption needed for the hardness of approximation with a better factor is not P not equal to NP. It is a stronger but still quite believable assumption about the hardness of NP-complete problems. (Noted by Yoshio Okamoto.)
• P. 237, Exercise 10.1.6(b), all of the inequality signs should be flipped. (Noted by Leonard Schulman.)
• P. 239, Epsilon net theorem: An additional assumption on the measure \mu is needed; for a pathological \mu the conclusion may fail (because certain functions in the proof are not measurable). The theorem is valid, in particular, for every Borel measure on R^n, and more generally on every Polish space (separable and metrizable by a complete metric). This should cover all cases one may normally encounter in discrete geometry. The precise measurability assumptions needed are stated in the Vapnik-Chervonenkis paper; one is in the first paragraph on the page 265 and another is in the middle of page 268 in the second paragraph of section 3. (Noted by Sergei Starchenko.)
• P. 241, l. 6, missing curly brackets {...} in formula. (Noted by Yoshio Okamoto.)
• P. 241, bottom displayed formula, 2er ln r r^{-C/4} should be 2eCr ln r r^{-C/4}. (Noted by Guy Even.)
• P. 250 l. -18: the visibility regions in the cited example from [Val99b] occupy 5/9 of the gallery (rather than 1/2). (Noted by Pavel Valtr)
• P. 251, 10.3.4b: a 1/r-cutting for H, not for L. (Noted by G"unter Rote.)
• P.254, middle. Grini should be Grigni. (Noted by G"unter Rote.)
• P. 257, the binomial coefficient {n-d+1\choose p-d+1} should be {n-d-1\choose p-d-1}, twice. (Noted by Uli Witting, Bonn.)
• P. 259, Theorem 10.6.1, and next page, Lemma 10.6.2: with the current argument in the proof of the lemma, we need to assume that the sets are compact. (Noted by Yoshio Okamoto.)
• P. 269, first displayed formula, the sum in the r.h.s. should be under expectation. (Noted by Gabriel Nivasch.)
• P. 275, the line lambda_v in the upper picture should be drawn one "floor" lower, so that the marked vertices lie on the middle level. (Noted by Micha Sharir.) The same adjustment for the lower picture (Noted by Gabriel Nivasch.)
• P. 276, end of the 2nd paragraph, the definition of d_i should be as on the previous page; that is, d_i is the number of intersections of l_i with l_j, j<i. (Noted by Gabriel Nivasch.) Later on, instead of "each line in the bundle of l_i has exactly d_i vertices of V_{m+1}" it should be "each line in the bundle of l_i has at most D_m vertices of V_{m+1}". (Noted by Guenter Rote.)
• P. 280, Exercise 1(a), k+1 should be replaced by 2(k+1); k+1 counts only the directed k-edges going from left to right. The same correction also applies to the hint to Exercise 2. (Noted by Gabriel Nivasch.)
• P. 285, Fig. 11.1, the horizontal segment in the leftmost devil shouldn't be there. (Noted by Gabriel Nivasch.)
• P. 286, in the outline of the proof of the improved k-set bound in dimension 3, n_p should be replaced by n throughout. Moreover, for the case where the chains C_1 and C_2 do not cross, we still need to distinguish two subcases: If both C_1 and C_2 end with infinite rays on both sides, then the argument in the outline can be applied. The other case, where at least one of C_1, C_2 ends with at least one bounded edge, needs to be accounted for separately: there are at most c_p n such pairs. (Noted by Uli Wagner.)
• P. 286, 6th line below the first picture, t\in {\cal T} should be T\in {\cal T}. (Noted by Yoshio Okamoto.)
• P. 287, top picture - the point q^* should be on the line pq, rather than on rq. (Noted by Yoshio Okamoto.)
• P. 291, Berge's Strong Perfect Graph Conjecture was proved by Chudnovsky, Robertson, Seymour, and Thomas, by graph-theoretic (as opposed to polyhedral) methods. See Chvatal's web page about it. Even more recently, a polynomial-time algorithm for recognizing perfect graphs was found by Chudnovsky, Cornuejols, Liu, Seymour, and Vuskovic (to appear in Combinatorica).
• P. 298 l. 3, x should be x_1. (Noted by Bernard Lidicky.)
• P. 298 bottom, in the "basic fact from measure theory" one should assume vol(X_1) finite (which is no problem in the application since the considered sets are compact). (Noted by Eva Kopecka.)
• P. 294 Exercise 2: K should be a MAXIMAL clique. (Noted by Robert Samal.)
• P. 300, 3rd line from the bottom: A+B should be (1-t)A+tB. (Noted by Robert Samal.)
• P. 301, end of "Bibliography and Remarks", the sets should be A,B,K_3,K_4,...,K_n and the left-hand side of the inequality should be V(A,B,K_3,...,K_n)^2. (Noted by Robert Samal.)
• P. 301, Exercise 2, A and B should be assumed nonenmpty. (Noted by Yoshio Okamoto.)
• P. 305 bottom, c_1 equals (1/(n+1))(h(b)-h(a)) (a and b exchanged). (Noted by Robert Samal.)
• P. 308 line -14 the right bar of the absolute value sign is missing. (Noted by Nati Linial.)
• P. 312, 4th line below the first picture, 2\pi e/n should be \pi e/2n. (Noted by Robert Samal.)
• P. 314 ex. 2, the integral should range over R^n, not R^d. (Noted by Nati Linial.)
• P. 315, 5 lines below Theorem 3.1.2, c^N should be c^n. (Noted by Robert Samal.)
• P. 317, the second paragraph ("By more refined consideration...") is oversimplified and confusing at best. Here is an attempt at a correct concise explanation: "By more refined consideration, one can improve the lower bound to approximately the square of the quantity just given. Having generated the query points x_1,...,x_N for B^n, we check that for K=conv {+e_1,-e_1,...,+e_n,-e_n,+x_1^0,-x_1^0,...,+x_N^0, -x_N^0}, with x_i^0=x_i/||x_i||, the oracle is free to give the same answers as those for B^n, and the same holds for the dual body K^*. A deep result (the inverse Blaschke-Santalo inequality) states that vol(K)vol(K^*) > c^n/n! for any centrally symmetric n-dimensional convex body K, with an absolute positive constant c, and together with Theorem 13.2.1 this yields the appropriate lower bound for vol(K^*)/vol(K). This improvement is interesting because for symmetric convex bodies it almost matches the performance of the best known algorithm." (Noted by Nati Linial.)
• P. 318, third line from below, "distance at most 1/n from S'" should be "distance at most 1/n from x". (Noted by Man-Cho A. So.)
• P. 319, we should (and may) also assume that N exceeds 2n, say, so that the formula defining k yields a value below n. (Noted by Robert Samal.)
• P. 320, 3rd paragraph of "Bibliography", line 6, the width of the slab should be 2/||u_i||, rather than 1/||u_i||. (Noted by Yoshio Okamoto.)
• P. 323 middle, treatment of the general case, we need the opposite inequality for q: q=O(n/ln(N/n)). This is an equally easy calculation. (Noted by Jeonghyeon Park.)
• P. 323, last line, the convex hull of the y^{(i)} is not a crosspolytope; one should speak about +y^{(i)} and -y^{(i)} or phrase the argument a bit differently. (Noted by Nati Linial.)
• P.324 line 11, "n special points" (instead of "d special points"). (Noted by Nati Linial.)
• P. 326, last line, y^{(i)} should be +- y^{(i)}. (Noted by Nati Linial.)
• P. 328 Exercise 3: the last inequality in (b) should be vol(E) <= max(vol(E_1),vol(E_2)), rather than vol(E) >= min(vol(E_1),vol(E_2)). (Noted by Kasturi Varadarajan.)
• P. 329 l. -12, the exponent of epsilon should be +2, rather than -2.
• P. 332 l. 6 (2nd line in the displayed formula), "=" should be "less or equal" (noted by Rados Radoicic)
• P. 333, Prop. 14.2.1, R^d should be R^n. (Noted by Nati Linial.)
• P. 339, Prop. 14.3.4, the dimension in the formula should be one smaller (ie. "-2" instead of "-1"), for otherwise, the calculation doesn't quite work. (Noted by Josef Cibulka.)
• P. 340, 2nd line of the last paragraph, "-lambda^2" in the exponent should be "lambda^2".
• P. 343, above Lemma 14.4.2, "2k facets" should be "2n facets". (Noted by Robert Samal.)
• P. 347, Exercise 1, k should be n (in R^k and B^k). (Noted by Yoshio Okamoto.)
• P. 348, Exercise 1, "Hammer" should be "Hanner" (my apologies to him).
• P. 350 lines 1-2, K should be \tilde K. (Noted by Yoshio Okamoto.)
• For a new survey on the topics of Chapter 15 see a handbook chapter by Piotr Indyk and me. Many open problems, with updates on recent progress, are listed in Open problems on embeddings of finite metric spaces.
• P. 361, notes to Section 15.2, 2nd paragraph from below, "16/epsilon^2" should be "4/epsilon^2". (Noted by Piotr Indyk.)
• P. 363, above the picture: "...is a tree" is not correct; this subgraph contains the tree but there may be extra edges connecting the leaves (which doesn't affect the argument, though).
• P. 371, bottom displayed formula, E_1 and F_1 should be interchanged in the right inequality. (Noted by Yoshio Okamoto.)
• P. 374, formula (15.3), ||x|| at the end should be squared. (Noted by Petr Kolman.)
• P. 376 l. 11, "\mu_2/n" should be "n/\mu_2". (noted by Rados Radoicic.)
• P. 378 top, phi and eta are interchanged (in the definition, on the line below the 2nd displayed formula, and 4 lines below). Moreover, the D^2 factor in the definition of x_{uv} should be present in the second case and not in the first, and the inequality in the next line should be \rho^2(\eta)-D^2\rho^2(\varphi)\geq 0. Other ways of fixing the confusion with eta and phi are possible as well. (Noted by Mikhail Ostrovskii.)
• P. 383 exercise 15.5.6, the sets A and B should form a partition of V, i.e., B=V\A. (Noted by Gabriel Katz.)
• P. 385, 3rd paragraph, 3rd line, max should be min (in the definition of f_i(u)). (Noted by Yoshio Okamoto.)
• P. 389, proof of Lemma 15.7.2: r_j should really be defined as the minimum of r_q and of the current definition. The argument as written works only for j with r_{j-1}< r_q, but for the other j we have Delta_j=0. (Noted by Uli Wagner.)
• P. 400, Exercise 15.7.9(a) last line, min should be max. (Noted by Yoshio Okamoto.)
• P. 407, Dvoretzky is misspelled (with "s" instead of "z").
• P. 409, hint to Exercise 1.3.5(c), the number should be \sqrt{d/(2(d+1))} instead of \sqrt{2d/(d+1)}.(Noted by Jie Gao.)
• P. 409, hint to Exercise 2.1.4(c), n^{d+1} should be n^{-(d+1)}. (Noted by Sergio Cabello.)