The Probabilistic Method (Part 2) - Spring 2012

Contact Information



Program and Examination

Week-by-week Schedule


Some Useful Links

   Contact Information

Lecturer 1 :   Peter Hegarty, Rum MV:L3032, Tel.: (031) 7725371,

Lecturer 2 :   Jeff Steif, Rum MV:H5017, Tel.: (031) 7723513,

Lecturer 3 :   Devdatt Dubhashi, Rum EDIT:6472, Tel.: (031) 7721046,


The course will meet on the following dates :

March 30; April 4, 18, 20, 25, 27; May 2, 4, 9, 11, 16, 18, 23, 25.

The times and locations are as follows :

Wednesdays, 13:15 - 15:00, Room MV:H11.

Fridays, 08:00 - 09:45, Room MV:L14.


Lectures will be based on a mixture of journal papers and textbook material. The teachers will present some material in the first two lectures. Thereafter all the presentations will be given by students. See the week-by-week schedule below for more details.

   Program and Examination

The teaching will involve only lectures , according to the schedule above. The first few lectures will be given by the teachers and build on material covered in Part 1 of the course from the Fall. Thereafter students will give lectures on selected topics. Examination will be by means of these student lectures.

   Week-by-week Schedule

As we proceed, completed material will be marked in green.

OBS! The following schedule is approximate and will be continuously updated.

[AS] refers to the 2nd edition of Alon-Spencer. Material from the book will be handed out in class.

Week Stuff Lecture Notes
13 Talagrand's inequality and applications :

Balls and bins, Eigenvalues of random symmetric matrices, TSP in the plane.

[AS], 7.6 - 7.7.
14 Complexity of randomised algorithms I. 1 2
16 Apr 18: Anders Martinsson.

Apr 20: Class cancelled.

17 Apr 25: Leonid Molokov: Circuit complexity and the Haastad switching lemma.

Apr 27: Dmitry Zhelezov: Janson's inequality and applications in random graphs and number theory.

Leonid: [AS], Chapter 11.

Dmitry: [AS], Chapter 8, and this. See also 1 2

18 May 2: Urban Larsson.

May 4: Timo Hirscher.



19 May 9: Magnus Önnheim.

May 11: Aron Andersson: Lovasz local lemma and applications to Ramsey numbers.

Magnus: 1 2

Aron: [AS], Chapter 5.

20 May 16: Wei Yang.

May 18: Class cancelled.

21 May 23: Joel Larsson: Complexity of randomised algorithms II.

May 25: Thomas Bååth Sjöblom: Discrepancy theory - Six standard deviations suffice.

Joel: See Week 14.

Thomas: [AS], Chapter 12.

22 May 30: Alexey Lindo: FKG inequality and applications to balls and bins. Alexey: [AS], Chapter 6 and this.


There will be no homeworks in this course.

   Some Useful Links

Om du har kommentarer, påpekanden eller annat att säga om kursen, tryck  

Peter Hegarty <>
Last modified: Wed Jun 06 07:50:00 CET 2012