Instructor Course Schedule Topics and Prerequisites Final Exam and Requirements Exercises Course Progress |
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 |
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. |
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. |
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. |
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 |
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 |