## Lectures on the Probabilistic Method

In first semester 2013 I will give some lectures on the Probabilistic Method of Paul Erdős.

### Time and place

The lectures will (usually) be held on Thursdays, from 3pm to 4pm, in Lecture Theatre V101 at the University of Newcastle, Callaghan campus (coordinates D4 on the campus map), starting on Thursday 7 March.

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

### Aims

I hope to give an introduction to the probabilistic method, covering some (by no means all) of the book by Alon and Spencer, and concluding with the proof of some recent results (with Judy-anne Osborn and Warren Smith) on maximal determinants of {+1, -1} matrices.

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 link to the paper by Alon and Krivelevich is broken, and should be replaced by this).

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).

• 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

For copyright reasons I can't make the whole book by Alon and Spencer available online (and anyway, you should get a copy yourself, either by borrowing it from the library or buying a copy). However, to get you started I have scanned a relatively small number of pages, as follows:
• 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)

Following are some minor things that I've noticed in the third edition (2008):
• 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 σ2, 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".