Prerequisites: Graduate Advanced Probability Course or 308-490 or 308-690.
There will be 3 homework assignments worth 50% and a presentation. worth 50%.
For a course description and list of references see:
We will mainly use McDiarmid's survey. and Lugosi's survey.
Thanks also to Shannon Starr for getting us a copy of A paper by Talagrand.
Lecture 1, September 1: Introduction and Chernoff Bounds Sections 1-3 of Lugosi and Section 2 of McDiarmid.
Lecture 2, September 8: The Chromatic Number of G(n,p) Section 5.1 of Molloy and Reed (handed out in class) and Section 3.1.2 of McDiarmid (plus references there)
Lecture 3, September 13: Efron-Stein and its Applications Section 4 of Lugosi
Lecture 4, September 15: The Bounded Differences Inequality Section 5.1-5.4 of Lugosi
Lecture 5, September 20: Combinatorial Entropies and the Lovasz Local Lemma. Rest of Section 5 of Lugosi, LLL reference yet to be determined, Assignment 2 handed out.
Lecture 6, October 4: Another Graph Colouring Application (Student Presentation) Chapter X of Molloy and Reed for an unknown $X$, Assignment 1 due.
Lecture 7, October 6: Martingales, Section 3.3-3.6 of McDiarmid
Lecture 8, October 13: An application to hypergraph matchings. Section 3.2.1 of McD and references there.
Lecture 9, October 18: Isoperimetric Inequalities, Section 3.1.3 of MCD and the section beginning on page 18 of MCD on permutation graphs
Lecture 9, October 20: Talagrand I, Section 4 of McDiarmid
Lecture 10, October 25: More on Talagrand and taking up assignment 1.
Lecture 11, October 27th: Random Polynomial, Ketan
Lecture 12, Nov 3rd: Taking up assignment II.
Lecture 13, Nov 5th, VC Dimension 1, Nicolas
Lecture 14, Nov 8th, VC Dimension 2, Ricard
Lecture 15, Nov 10th, Isoperimetric Inequalities, Arkhadev
Lecture 16, Nov 15th, The Infamous upper tail, Erin
Lecture 17, Nov 17th, Hayward and Mcdiarmid, Concentration for Quicksort, Michal
Lecture 18, Nov 22nd, Vojkan
Lecture 19, Nov 24th, Vojkan
Lecture 20, Nov 29th, Vojkan
Lecture 21, Decmber 1st, Vojkan
Student presentations will begin on October 27th. The three lectures missed in September will be made up by having some of the student presentations on Fridays in November.