# Geometric discrepancy (An illustrated guide) by Jiri Matousek

### Some striking new developments in combinatorial discrepancy in 2010-11

• Bansal's algorithm for computing low-discrepancy colorings, based on semidefinite programming, which makes a number of bounds obtained by the partial coloring method constructive.
• Hardness results of Charikar, Newman, and Nikolov: it is hard to approximate the combinatorial discrepancy with factor better than n^{1/2}.
• The discrepancy for 3 permutations is of order log n, as a lower bound by Newman and Nikolov shows.

### A revised second printing is out (January 2010)

with known errors fixed, references updates, and with a short appendix describing new developments. The appendix plus the updated bibliography can be found here.

## Errata for the second printing (2010)

• P.2, picture, the notation doesn't match the text above, a_2 and b_1 should be interchanged. (Noted by Chris Lawton.)

## Errata for the first printing (1999)

• P. 16 Exercise 3, the first subscript 2 should be d.
• P. 21, 2nd line of the formula beginning with "eta=", the sum should be from j=1.
• P.49 last line, the sum should be up to K-1, not K. (Noted by Michael Gnewuch.)
• P.53 3rd line above Prop. 2.7, m_k should be m_d. (Noted by Michael Gnewuch.)
• P.54, last line of Th. 2.9, box of volume b^{-m+q} instead of b^{m-q}. (Noted by Michael Gnewuch.)
• P.60, bottom displayed formula, sgn^{pm}(b'_{t+1}-b_{t+1}) should be sgn^{pm}(b_{t+1}-b'_{t+1}), with the same swap once again on the next page. (Noted by Michael Gnewuch.)
• P. 108 Exercise 1, missing factor (1/m) under the square root sign (the inequality should read \disc_2(S) \ge \sqrt{(1/m) \trace(D)}). (Noted by Benjamin Doerr.)
• P. 174 last line, the formulas for a and for b should be interchanged. (Noted by Adrian Dumitrescu.)
• P. 178 bottom, a serious mistake in the proof of Baker [Bak] was discovered by J. Beck. In 2008 Bilyk, Lacey, and Vagharshakyan proved a better lower bound; see "New developments" below.
• P. 179 Exercise 2(a) is wrong. A counterexample was constructed by Beck, and this is the flaw in Baker's proof mentioned in the previous comment.
• P. 243, the lower bounds for D(n,R^d) and for disc(n,R^d) should be changed according to the remark to page 178.
• Hint to Exercise 2.1.3: there are many points ON the diagonal x=y; the empty rectangle should be taken near the diagonal but not containing it.
• Hint to Exercise 4.1.1: (n-2\Delta)/(n+2\Delta) should be (n-4\Delta)/(n+4\Delta), and consequently, the 12 later should become 24. (Noted by Benjamin Doerr.)