Part C Probabilistic Combinatorics

HT 2008

Lecturer: James Martin (email martin (at) stats.ox.ac.uk)
Class tutors: Christina Goldschmidt and Atsushi Tateno
Teaching assistants: Yilei Hu and Matthew White

Timetable

Lectures: HT 2008 weeks 1-8: Tuesday 9am and Wednesday 12pm in Lecture Room 3 (Maths Institute)
Classes: Wednesday afternoons weeks 3-8. Hand in by 9.05am Tuesday in the basement of the Maths Institute.
The final classes will be on TUESDAY of Trinity Term week 1, at 2pm, 3pm and 4pm in Lecture Room 2 (Maths Institute). Please hand in by Monday noon in the Maths Institute basement.
Here are the classlists.
Trinity Term consultation time: Thursday 22 May (week 5), 2-3.30pm, Statistics Dept, 1 South Parks Road, first floor teaching room. If you have queries about the course during your revision, you are also welcome to contact me by email.

Example sheets

Example sheet 1 (to be prepared for the classes in Week 3).
Example sheet 2.
Example sheet 3.
Example sheet 4.
Example sheet 5.
Example sheet 6.
Example sheet 7. See above for details of the last class.

Here is a practice paper with some approximately exam-like questions (prepared for last year, since there were no previous exam papers at that stage). Question 4 is probably a bit long for a real exam question. Here is last year's exam paper.

Remarks on Azuma, concentration of Lipschitz functions, isoperimetric inequalities, etc

When doing the isoperimetric inequality in lectures, I cheated inadvertently by using a stronger version of the result on concentration of Lipschitz functions than I had previously proved. Thanks to a couple of people for pointing this out! Here are some notes to clarify things (for those who are interested - the details are not important for the exam or anything).

Books

The lectures will be self-contained - but reading around the subject is very much encouraged! The main reference for the course is

The Probabilistic Method, by Noga Alon and Joel Spencer. 2nd ed., Wiley 2000.

Also recommended (although maybe less easy to get hold of) are some of the articles in

Probabilistic Methods for Algorithmic Discrete Mathematics, ed. M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B.Reed. Springer 1998.

For the section on random graphs, two recommended books, going a very long way beyond what will be done in the course, are

Random Graphs, by Bela Bollobas. 2nd ed., CUP 2001.
Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley 2000.

The paper I mentioned by Asaf Nachmias and Yuval Peres about the "critical random graph" G(n,1/n) can be found here.

Other books which cover material relevant to the course include

Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by M. Mitzenmacher and E. Upfal, CUP 2005.
Graph Colouring and the Probabilistic Method, by M. Molloy and B. Reed, Springer 2002.
Randomized Algorithms, by R. Motwani and P. Raghavan, CUP 1995.
Additive Combinatorics, by T. Tao and V. Vu, CUP 2006