The Probabilistic Method

Summer 2016

Instructor

Course Schedule

Topics and Prerequisites

Final Exam and Requirements

Exercises

Course Progress 		Image

Instructors

Tibor Szabó Tamás Mészáros Shagnik Das
Arnimallee 3, Rm 211a Arnimallee 3, Rm 205 Arnimallee 3, Rm 204
szabo at math dot fu-berlin dot de tamas dot meszaros at fu-berlin dot de shagnik at mi dot fu-berlin dot de
838-75217
Top of page

Course Schedule

Lectures will take place in Arnimallee 6, SR 031, on Tuesdays from 12:30pm to 2:00pm.
Exercise classes will take place in Arnimallee 3, SR 119, on Wednesdays from 12:30pm to 2:00pm.

On the first week, the exercise class will be replaced with a second lecture.
Top of page

Topics and Prerequisites

Topics

 In this course we will survey the probabilistic method and its applications in combinatorics, geometry and theoretical computer science.

Specific topics include linearity of expectation, alterations, the second moment method, the Local Lemma, correlation inequalities, martingales, concentration inequalities, pseudorandomness and random graphs.

Prerequisites

 Basic combinatorics and graph theory, probability, linear algebra and calculus.
Top of page

Final Exam and Requirements

Final Exam

 The grade for this course is based solely on the final exam. There will be oral exams, offered during the week of September 12 and again during the week of October 10. During the exam, you should expect to encounter three different types of exercises: material from lectures, homework exercises, and new exercises.

Requirements

 A full description of the formalities of the course and the requirements for successfully completing the course can be found here.
Top of page

Exercises

Homework assignments will be posted below, and should be submitted at the beginning of the exercise classes. Alternatively, they may be submitted to the tutor box of Tamás Mészáros in Arnimallee 3.


Assignment Due date
Sheet 1 27/4/2016
Sheet 2 4/5/2016
Sheet 3 18/5/2016
Sheet 4 25/5/2016
Sheet 5 8/6/2016
Sheet 6 22/6/2016
Sheet 7 6/7/2016
Sheet 8 20/7/2016
Sheet 9 at exam
Top of page

Course Progress

Material from this course can be found in The Probabilistic Method by N. Alon and J. Spencer.


Lecture notes about the story of R(3,k) and the Galton-Watson process


Date

Topics

References
19/4/2016 First moment: union bound and linearity of expectation; Application: k-SAT
20/4/2016 First moment applications: Schütte property of tournaments, sum-free sets, asymmetric Ramsey numbers Ch 1
26/4/2016 R(4,k) lower bound, Alterations: lower bound on the independence number of arbitrary graphs; the story of R(3,k): first bounds. Ch 1, Lecture notes
3/5/2016 finding the closest vertex in a parallelepiped; maximum number of Hamilton cycles in a tournament. Sec 2.1, Probabilistic Lens (Ch 4)
10/5/2016 proof of Bregman's Theorem. Probabilistic Lens (Ch 2)
11/5/2016 Application of linearity of expectation: proof of Turán's theorem; lower bounding the packing constant of convex centrally symmetric bodies; bounding the domination number of a graph in terms of its number of vertices and minimum degree. Probabilistic Lens (Ch 6), Sec 3.4, Sec 1.2
17/5/2016 Chebyshev's Inequality, Application: number of copies of a fixed graph H in G(n,p). Lecture notes (also Sec 4.4)
24/5/2016 Further improving the lower bound of R(3,k) (Krivelevich's proof), Erdős-Tetali Lemma, Chernoff bound Lecture notes
31/5/2016 Upper bound on R(3,k) (Shearer's proof); Erdős problem on sets with distinct subsets sums Probabilistic Lens (Appendix); Sec 4.6
1/6/2016 Concentration of the clique number; Block designs Sec 4.5; History of block designs
7/6/2016 Conjecture on the Existence of Designs, Rödl's Theorem, Pippinger's Thoerem Sec 4.7; On the Existence Conjecture
14/6/2016 Nibble Method at work I Sec 4.7
15/6/2016 Nibble Method at work II Sec 4.7
21/6/2016 Nibble Method at work III, Local Lemma for proper 2-coloring of hypergraphs Sec 4.7; 2-coloring Local Lemma
28/6/2016 k-fold coverings, statement and application of symmetric Local Lemma Sec 5.2, 5.4;
29/6/2016 the symmetric and the general Lopsided Local Lemma, independent transversals Sec 5.1, 5.5;
5/7/2016 Latin transversals, R(3,k), Correlation Ineqqualities, monotone properties Sec 5.3, 5.6, Chapter 6;
12/7/2016 Four Function Theorem, FKG inequality Sec 6.1, 6.2, 6.3
13/7/2016 Martingales, Azuma's Inequality, Edge-exposure, vertex-exposure Sec 7.1, 7.2
19/7/2016 graph parameters satisfying the Lipschitz condition, chromatic number of the random graph Sec 7.3, 7.4
Top of page