Lectures on the Probabilistic Method

Time and place

I will be away on 30 May so there will be a guest lecture on that day.

Aims

Since I am by no means an expert in the probabilistic method, audience participation is welcomed, even necessary. I hope we can learn something about the probabilistic method and its applications by trying to understand Alon and Spencer, and perhaps some of the original papers.

Main Reference

• Noga Alon and Joel H. Spencer, The Probabilistic Method (third edition), John Wiley and Sons, 2008.
  [All three editions are available in the ANU Hancock Library.
  The second (2000) edition is in the University of Newcastle library, call number 511.6 ALON 2000.
  The first ten chapters are much the same in the second and third editions.]
  We'll cover selected chapters of this book, starting with Chapter 1, followed by my (draft) paper arXiv:1211.3248v2.

Other References

• The Wikipedia page on the Probabilistic Method is not a bad place to start
  (the link to the paper by Alon and Krivelevich is broken, and should be replaced by this).

• Paul Erdős and Joel Spencer, Probabilistic Methods in Combinatorics, Akadémiai Kiadó, Budapest, 1974. Also published by Academic Press, New York, 1974.
  An early book on the probabilistic method, much shorter than Alon and Spencer.
  [Available in the ANU Library and the University of Newcastle Library, call number 511.6/15.]

• Richard P. Brent, Judy-anne H. Osborn and Warren D. Smith, Lower bounds on maximal determinants of +-1 matrices via the probabilistic method, 3 Dec 2012, arXiv:1211.3248v2.
  The results in this paper explain why I recently became interested in the probabilistic method.
  Of course, there are many other applications of the probabilistic method that may be of more interest to you!

• Most of Pál (Paul) Erdős's papers are available from the Alfréd Rényi Institute.
  This includes all the papers mentioned in Appendix B.1 of Alon and Spencer.

• Open Problems by Paul Erdős (from the first edition of Alon and Spencer; some of these problems may no longer be open).
  See also Appendix B.2 of Alon and Spencer (third edition).

• Noga Alon's homepage is here (includes links to a course Probabilistic Methods in Combinatorics and many papers available online).

• Joel Spencer's homepage is here (includes many papers available online, and his Nine Lectures on the Probabilistic Method [warning - pages are in reverse order]).

Excerpts from Alon and Spencer

• Front matter (Table of Contents, Preface etc)
• Chapter 1: The Basic Method (includes The Probabilistic Lens: The Erdős-Ko-Rado Theorem)
• Chapter 2: Linearity of Expectation (includes The Probabilistic Lens: Brégman's Theorem)
• Chapter 4: The Second Moment (Sections 4.1 - 4.4 only).
• Appendix A: Bounding of Large Deviations
• Appendix B: Paul Erdős (the papers of Erdős mentioned in Section B.1 are
  1935-01, 1947-09, 1940-12, 1956-17, 1963-06, 1964-08, 1960-10, 1959-06, 1961-06, 1962-10 and 1973-10 at the Alfréd Rényi Institute website).
  Although the content of many of these papers is summarised in Alon and Spencer, it is always worth reading the original papers.
• References (more than 200 references on the probabilistic method)
• Author and Subject Indices
• For other chapters, you could try Joel Spencer's archive (pages in reverse order; roughly corresponds to the first edition, so chapters 11 and 17 of the third edition are missing, and chapters after chapter 10 are numbered one less than in the third edition).
  Note: to reverse the page order, first convert from ps or eps to pdf (if necessary) using ps2pdf, then use pdftk to reverse the page order,
  e.g. pdftk chap1.pdf cat 10-1 output chap1-fixed.pdf
  (does anyone know an easier way?).

Errata for Alon and Spencer (third edition)

• Page 1, line 4 of Sec. 1.1: Delete "and then shows that the desired properties hold in this structures".
• Page 4, Theorem 1.2.2: The graph G must be simple (this might be a hidden assumption in other Theorems too).
  Assuming that G is simple, the result seems to hold for all nonnegative delta, so the condition delta > 1 is not necessary.
• Page 43, Theorem 4.1.1: The one-line proof implicitly divides by σ², so there is an implicit assumption that σ > 0.
  If σ = 0 then the statement is incorrect, but could be fixed by changing "≥" to ">" in line -2.
• Page 308, line 4, "Proof": this refers to the proof of Theorem A.1.1, not the proof of Markov's inequality.
• Page 309, third displayed equation: the denominator "sqrt{2πa}" should be "sqrt{2π}a".