Structure and Randomness: pages from year one of a mathematical blog

Terence Tao

American Mathematical Society, 2008

298 pages

ISBN-10: 0-8218-4695-7

ISBN-13: 978-0-8218-4695-7

mbk-tao-cov_0001

This is a book version of my blog, covering many (though not all) of my articles in 2007, reworked into a publishable format (and in particular, with formal and updated references).

A draft copy of the book is available here. Note that the formatting for this internet version is significantly different from that in the final print version, in particular the page numbering does not correspond at all.

Here is a (2MB) PDF file containing the front cover of the book.

The official AMS web page for this book is here.

A review of the book for the American Scientist is here.

Here is a review for the MAA.

— Errata —

  • Page 51: In Lemma 1.34(2), hf'(x) should be hL.
  • Page 54: The phrase “nonstandard ultrafilter on {*} {\Bbb N}” requires some clarification.  It should be “ultrafilter on {*}{\Bbb N} that extends an ultraproduct of nonprincipal ultrafilters on {\Bbb N}“.
  • Page 95, Figure 1: The graph of K_{3,3} is missing two edges (namely, the long diagonal edges between opposite corners of the graph).
  • Page 101: Footnote 67 is incorrect and should be deleted.
  • Page 102: (A+A) \times (A \cdot A) should be (A \cdot A) \times (A + A).
  • Page 128: In the second and third displays, \frac{1}{t^{p(1-p)}} should be t^{p(1-p)}.
  • Page 129: “decaying faster” should be “decaying faster or having smaller amplitude”.
  • Page 143: The proof that 1/\alpha \leq \hbox{maxflow} is not correct as stated (the perturbations indicated do not preserve the property of being an \alpha-flow).  A correct argument is as follows.  Call an edge of an \alpha-flow unsaturated if it has weight strictly between 0 and \alpha, and similarly call a vertex unsaturated if its net inflow or outflow is strictly less than \alpha.  Observe that if e is an unsaturated edge, then the final vertex u of e will either have an unsaturated edge leading out of it (if u is unsaturated) or another unsaturated edge leading into it (if u is saturated).  Similarly, the initial vertex u’ of e will either have an unsaturated edge leading into it (if u is unsaturated) or another unsaturated edge leading out of it (if u is saturated).  Thus, if there is at least one unsaturated edge, then by iterating the above observations, one can find an oriented cycle along unsaturated edges with the property that at any saturated vertex u, the number of edges flowing along the cycle into u equals the number of edges flowing against the cycle into u, and the number of edges flowing along the cycle out of u equals the number of edges flowing against the cycle out of u. For this cycle, one can modify the flow as indicated in the text to reduce the number of edges in the \alpha-flow.
  • Page 137: In the last line of Case 1, “multiply (1.47) by…” should be “raise (1.47) to the power r' and then multiply by…”, and r+r' should be (r+1)r'.
  • Page 148: In the first line, \overline{F_v} = \overline{F_{-v}} should read F_v = \overline{F_{-v}}.
  • Page 180: In the second display, x/\xi should be x \xi.
  • Section 1.11?: The inequality |E| \leq 3|V| - 6 is only valid for connected graphs with at least one cycle.  In general, one only has |E| \leq 3|V|.  One must then delete all terms involving the number 6 in the rest of the section.  One can then replace “To solve the optimisation problem exactly, one needs to solve a cubic; but we can perform a much cheaper computation” by “One can solve the optimisation problem exactly, but we can perform a cheaper computation”.
  • Section 2.10?  In (2.8), \sum_d |\lambda_d| should be \sum_d |c_d|.

Thanks to Ravindra Bapat, Dion, Tobias and Tony, Norman Hardy, Matthew Kahle, JamesL, Avi Levy, Arturo Magadin, Kirane Mokhtar, David P. Moulton, Nikodem Szpak, Sheng-Peng Wu, and Yuncheng  for corrections.